First A* Implimentation

ArmchairArmada on 2011/09/15 06:25

I've been wanting to try to write an implementation of A* for a while, and I finally bit the bullet and wrote one today.  It turned out pretty good I think.  Maybe it's not the most optimized it could be, but it works pretty well.  Currently, with the size maps shown in the screen shot, it usually takes less than 20ms to find a path or a little over 60ms if it cannot find any valid paths.  That should work out well enough -- especially since the algorithm will only be run when the player clicks on where he wants the mutants to go.

(log in to comment)

Comments

ArmchairArmada on 2011/09/15 06:38:

Noticed a few cases where it doesn't find the shortest path, but instead one that's a little bit longer.  I think I know why it's doing that, but I'm not sure how much I'm going to worry about it.  I don't think it would adversely effect gameplay too much.

Hugoagogo on 2011/09/15 07:13:

I would estimate that it happens because of whatever heuristic you have used, if you remove a little bit of the bias towards the exit i think it would help it get the shortest route, at the cost of being slightly slower.

Whats horrible is trying to write an a* program that is able to path-find around a maze in a bitmap image

ArmchairArmada on 2011/09/15 07:49:

Yeah, I'm pretty sure the problem is pretty much what you said.  I actually only once noticed it take a longer than expected path, so the problem is rare and I'm not too concerned about it.

This will be used with a tilemap world.  Yeah, doing a per-pixel A* path finding on a bitmap would be a little slow, I suppose.

Hugoagogo on 2011/09/15 08:44:

I meant trying to generate accurate nodes to path find on one as well, also how is your maze generated?

ArmchairArmada on 2011/09/15 21:00:

I just randomly threw a bunch of walls in there to test the path finding.  This isn't a screenshot of my game, it's just a small program to test the A* implementation.