= 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.
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.
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*.
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.
Current improvements that I already realize need to be made are:
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.
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.
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 :)
Here are 3 links that I consider to be quite helpful:
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
Rant about nav-meshes vs waypoints, nice to read -> http://www.ai-blog.net/archives/000152.html
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 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.
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.
so… go ahead by all means 
