A* Search

[durnurd]

I figured somebody had better eventually implement the A* search algorithm, so here is the code project, and a sample project that uses it.  It could use some clean up, certainly.  A few things are more hard-coded than I'd like, but it's pretty good for 6 hours work.

And on the plus side (like this isn't enough), I now know how A* works much better than before.

Note: It's using a Manhattan Distance heuristic, because it's simple to implement.  I may look up a better one some time.

[durnurd]

I've implemented a few more heuristic algorithms, and played with a few numbers to get the movement to be a little smoother (since searching is tile-based and movement is not).  I implemented a Diagonal-shortcut heuristic and a Euclidean-distance heuristic.  I also added a default-0 heuristic for absolute-best path, which is not useful for most game-related cases.

Anyway, I'll probably post an updated version tomorrow.

[bluemonkmn]

I haven't looked at it in detail, but it's cool that you're doing this, and I'm thinking of ways to improve it.  (I was thinking of doing something like this myself, but clearly you're now more qualified to do it since you seem to know all the terminology and methods, fresh in your head.)  It looks like you might be calculating the whole path in 1 call.  Is there a way to split out the work like GoldYoink did so that a limited number of steps can be performed each frame?  This would allow you to call the function to update a (part of the) path each frame so that you can try to follow a moving target.  Basically it assumes the target hasn't moved until it finishes finding the path, then it re-starts with the target's new location.

Can you turn this in as a project for some class you're taking?
How do you know so much about search algorithms all of a sudden?  Is it from a class or from independent research?

[durnurd]

The Manhattan Distances heuristic I knew from a class I took a few years ago.  The rest I just looked up yesterday.  It's nice that I can sound informed on the subject after looking at a few web pages

The first thing I was thinking of was trying to get the path to be straighter, since the sprites don't need to move in orthogonal directions.  I changed the force used to push the sprite to be lower, and the TargetDistance to be a little higher, and that helped, but as for taking out unnecessary points in the middle, well, I don't see an immediate way to do that.  The next thing to do would be to make an algorithm to follow a moving target.

I did modify the sample project to call an update function every 35 frames and I added a player sprite so that it always moves toward the player.  I didn't notice any slow-down, and it seemed to work quite well.  I don't know fast it would go if I added more sprites, but I don't think it would be too bad.

Also, I don't think I quite understand how the GoldYoink search worked.  Did it just not move the enemy while the first search was being performed, then continue along the old path while the new path was being calculated throughout several frames?  I suppose the up-side of this would be less time per frame spent searching, but I haven't noticed any slow-down yet with doing it all in one frame, so I don't see a big necessity to spread it out, just yet.

[bluemonkmn]

Yes, I think the enemy was just left without any idea of which way to go for a short while, and then it would lag a little bit if the player moved to a location that would cause the shortest path to make the enemy want to go in a completely different direction.  The enemy wouldn't see that new direction for a few frames until the the path reached all the way to the enemy's position (often times a moving target doesn't drastically change the seeker's path, though, unless you're doing something like running around a large circle (tree or table for example) and you suddenly get closer on the opposite side).

The thing that has me worried is that for long or complex paths, or when there is a lot of other work going on (nearing the threshold of making the work take longer than 1 frame) performing some periodic operation on one frame might make the game jerky -- every 35th frame might last 2 frames instead of 1.

(999th post!)