# A* pathfinding with StandardGame

= EDIT = More effective code a couple of posts down = EDIT =

I have made a test application showing the use of A* path-finding with StandardGame. The graphics and original A* algorithm is from an applet version of this demo at http://www.cokeandcode.com/pathfinding.

The webstart is available here: AStar Example

Here’s a screenshot:

The source code is available here: http://www.mindgamer.net/webstart/astar/src/

Diagonal movement costs as much as horizontal and vertical. Left-click to select and move units, right-click to de-select. Red tiles mark the path A* chose, white ones are the tiles it visited while searching. As you can see from the screenshot already, this thing is far from perfect at this point. The reason I am posting it is two-fold.

1. With a little further improvement, I think it could be a nice additional example to the tutorial or WiKi section, offering newcomers a fast way of seeing how to use A*.

2. I truly hope that some of you experts have a free 5 minutes to look at the code and offer some advice on how to make it more effective and better structured, imagining the pathfinding used in a bigger project and map.

• Replace the current SortedList Open list with a binary heap
• Improve the heuristics or just check out the pathfinding itself a bit more - does not offer optimal path at this point
• Possibly organize the better the structure of the objects in the scene. Currently a HashMap is maintained that keeps track of which scene element is which unit. Need to implement a nicer approach as discussed in this thread.

Please feel free to offer me further advice on how to improve the code while keeping it still easy to maintain in light of possible use in a larger game.

Nice…

Have not delved into the code, but hope that an A* test like this will wind its way into the JME source.

Good thing… nice work mindgamer.

just a random thought:

one optimization i am using in hhexen is to check if a node is directly reachable form the current one. if yes, skip all nodes which are between them. repeat from that node. i could post my a*-implementation. there is one seacher class and an abstract node which has 2 implementations so far (a low memory/high performance grid node and a not so low memory/slower arbitrary positioned node).

I am not that concerned with a straight path to the target as long as it is optimal. In the picture posted, the path is obviously NOT optimal. I have not had a chance to look into the A* itself yet, but I am sure this error can be removed… I have played around with A*-s before a bit and it seems like a trivial situation to stumble upon.

I have been hoping you would offer us the chance of pick your A* apart so… go ahead by all means

I am not that concerned with a straight path to the target as long as it is optimal. In the picture posted, the path is obviously NOT optimal. I have not had a chance to look into the A* itself yet, but I am sure this error can be removed.. I have played around with A*-s before a bit and it seems like a trivial situation to stumble upon.

The error is probably in the heuristic calculation, I've found that some formulas are more optimal than others. I will try to post my solution once I have access to my code/IDE.

you can fix that by making diagonal movement about twice as expensive as straight movement.

straight 10

diagonal 20

[pre]

…#########…

…####################xxxxxxxxx#…

…xxxxxxxxx#…

…xxxxxxxxx#…

…xxxxxxxxx#…

…xxxxxxxxx#…

…xxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx#…

…xxxxxxxxxxxx#…

…x#…

…x#…

…x.#…

…x…#…

…xxxx#x.x.x.x.

…x…#…

…x…#…

…xxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…#…

…#…

[/pre]

straight 10

diagonal 10

[pre]

…#########…

…#…#xxxxxxxxx#…

…#…#.xxxxxxxxx.#…

…#…#…xxxxxxxxx…#…

…#…#…xxxxxxxxx…#…

…#…#…xxxxxxxxx…#…

…#.########…xxxxxxxxx…#…

#xxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxx…#…

…x…#…

…x…#…

…x…#…

…x…#…

…xxxx#x.x.x.x.

…x…#…

…x…#…

…xxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx…#…

…#…

…#…

[/pre]

Not your code btw, it's my own implementation. Still, results should be almost the same (some variation is possible, depending on the order of scanning new nodes).

OK, I have uploaded a new version of the same program. Well not quite the same. I have a new A* and also implemented Binary Heap for the open list. Some other small modifications also. (A* implementation inspired by http://www.policyalmanac.org/games/aStarTutorial.htm) Most implementations are used through interfaces etc. Anyways in case someone wants to use either the A* part or the Binary Heap, feel free. I think both are decently commented for making sense.

Here is the source rar-ed together

Here is the webstart link: http://www.mindgamer.net/webstart/astar2/AStar.jnlp

And here is a new screenshot:

Edit: Oh, right - diagonal movement costs 14 now, horizontal and vertical movement cost remains 10.

And yes, it would be very interesting to see your code once you get your pathfinding finished. If you would not mind, we could then even put it at the jme-demos google-code page Core-Dump started.

What kind of pathfinding are you developing by the way?

I agree with you: it wouldn't be bad if jmonkey included some basic AI.

The thing is, the world of game AI is huge, and there is not a specific implementation that fits all your particular needs.

Actually, though grid-based pathfinding is really helpful at times, jmonkey, as a 3d engine, should rather make use of any graph-based approach to the world space representation. You have more info on that at the provided links.

HamsterOfDeath: the technique you've suggested is called String-pulling. It's nice that you made it up all by yourself :D gratz!

BTW, I'm developing pathfinding for my current project. Ill be glad to share the code when it's done :)

Champandard's article to pathfinding algorithmics -> http://ai-depot.com/BotNavigation/Path.html
Overview on world space representations -> www.cse.lehigh.edu/~munoz/CSE497/classes/BaderPathfinding_2_1.ppt

I hope this helped someone ;D

Hi! I have copied this. Thank you very much for sharing.

(Also, please let me know if you wish to discuss this).

It's tricky to implement A* right.

Speed optimization is really import, and that means choosing the right data structure(s) for the open and closed lists.

Most often people implement only one data structure for the open or closed lists, but in reality you need to combine TWO datastructures as one (priorityqueue and hashmap are my favorite) to make sure all those operations on the list are O(1) or very close to it.

I've done a ultra-fast implementation of A* in Java, which I can try to dig up.

I've not really studies Kevglass's A* implementation carefully, but it doesn't seem to be very fast, nor to the paths look all that great

I've done a ultra-fast implementation of A* in Java, which I can try to dig up.

So, have you dug up the code and post it here?

Roslan

I don't if anyone is interested, but I've got an A* implementation in Java that's very easily pluggable.  It seems pretty fast to me, but I've not benchmarked it or anything.  If anyone wants the source, I'll post it here.

Steve16384 said:

I don't if anyone is interested, but I've got an A* implementation in Java that's very easily pluggable.  It seems pretty fast to me, but I've not benchmarked it or anything.  If anyone wants the source, I'll post it here.

that would be cool

This forum only allows pics, so it's on my server here: http://nologinrequired.no-ip.org/astar.zip

It should be self explanatory, though there are brief instructions in AStar.java, but feel free to ask any questions.

Hi

I’ve done an implementation of PRA* based entirely on this paper :

Partial Pathfinding Using Map Abstraction and Refinement

Nathan Sturtevant and Michael Buro

i don’t know if anyone is interested in this ?

I think it would be good to start a new topic, as this one has not had much activity for a year.