A*Pathfinding with some extra features

Posted by Glen on Oct. 12, 2014, 5:39 p.m.

So, I've been re-writing an old A*Pathfinding script from the gm6 days. I've converted it to GM:Studio and added some new features that it lacked in the past and that current available scripts don't have implemented.


Object determines path and begins moving along the calculated path. What happens when suddenly an object moves into your path?

Two things usually happen in A* algorithms. The script may generate fixed paths that do not change until the object has reached it's destination or something collides with the object. Others might recalculate the best path immediately.

But, what if the object that crossed your path continues to move and is no longer on your original "shortest path"? There's no reason to continue along your adjusted path if it isn't the shortest path to your destination. In games, I don't feel like the AI should always know the best option in the event of an unexpected change. I've added a range of view to the ai. If the object detects a new change within the original path and is within it's "range" it can decide to make the best decision. The same goes for when the original change reverses. If the object is now moving away from the unexpected change and is still within it's range, it can decide to go back to the original path if that change no longer effects it's goal.

I also added terrain penalties and boosts. But, I decided not to consider them in the A* path process. Once again, I feel like the ai should not know everything about the playing field. And so the effects are applied as the object moves over them.

My main goal with the changes was to make the pathfinding object make decisions based on an experienced situation. Make choices based on what is happening in front of you, avoid being a "know it all", and reuse what has worked for you in the past. This is somewhat how humans act.

Here's an example of what I have so far. I color coded all the sprites.

white: walls

green: path

red: movable walls. use arrow keys.

aqua: player

yellow: target

blue: slow down terrain

pink: speed up terrain

orange: player decision range

The players object restarts it's position when it reaches it's goal. Use the red walls to block it's path and observe behavior.

Link: http://files.64digits.com/Glen/pathfinding.exe


Nopykon 9 years, 8 months ago

Works well as far as i can tell, nice job.

Acid 9 years, 8 months ago

Your blog is cute.

Edit: Albeit a little broken.