This site requires JavaScript, please enable it in your browser!
Greenfoot_back

Report as inappropriate.

Glider_thumb
theguywholikeslinux presents ...

2011/9/8

A* Pathfinding

In a 2D top down game I am making I intend to have a fairly decent AI that can navigate around the world in a realistic, efficient and competitive manor. This scenario operates on a grid based world, but the scenario that I intend to use my A* algorithm on is a much higher resolution, so I plan to make a second version of this with a pixel based resolution and rather than using a grid I will use probably triangles that are the correct shape and size.

Source is available under a GPL 3.0 licence or later.

My current implementaiton has a "nodeMap" object on each grid tile that stores an object reference to each of it's adjenct nodeMaps or null (eg at the edges of the world). The actual searching algorithm isn't particularly advanced compared to most A* programmes, but the point is that I made it all by my self and it is a base to work off from when I try to make it work in higher res worlds. Basically what it does is on the start node it creates a "nodeSearch" object that stores the cumulative cost to get there, the nodes parent (or null for the start node), and the F score. I then explore each of it's neighbouring nodes that are not null or untraversable (black/wall). Out of these I only acutally explore them if they have not already been explored (in the closed list), or if we have already found them I only explore them if our cumulative cost is less than what we have already found (sometimes you will see the numbers on the nodes change, that is when the pathfinder has found a shorter route to the same node.) So the algorithm keeps on exploring, trying out the nodes closest to the finish first (because of the heuristic) until it findes a path. This path can then be reconstructed by examining the parent node of each nodeSearch object in turn until you reach the start again. I have made it so that the algrithm only expands one node per an act so you can use the speed bar at the bottom to watch it happen in real time if you want.

Currently I support 4 and 8 way movement (8 way in this example) and heuristics of:
- 0 (Dijkstra's algorithm)
- Manhattan
- Manhattan with straight line vector tie breaker (slightly (*0.001) prefers nodes that are directly in line between the start and the finish. Although it doesn't make a difference in the example as it is 8-way, it does in 4-way though.

===========================================
==========WHAT THE NUMBERS MEAN============
===========================================
BLUE: The blue number in the top left is the cumulative cost of the fastest route of getting to that node. (i.e it costs 1 for each node you travel up, down, left, or right and slightly more diagonally)

GREEN: The green number in the top right is the heuristic. It is basically an estimate of how much further we have to travel to get to the finish node assuming there is nothing in the way. That is what makes the program try the nodes that are closes first.

ORANGE: The orange number in the bottom left is the F Score, this is simply the blue number + the green number and it tells the pathfinder which node to try next, the ones with the lowest F score are tried first.


==========================================
================HOW TO PLAY=================
==========================================
FIRST PRESS RUN

To place the Start (green) node press "s" and then click where you would like it to be.
To place the Finish (red) node press "f" and then click where you would like it to be.
To make a node untreversable (make a wall) just click on it.

ONCE YOU ARE DONE PRESS THE [SPACE] BAR TO START THE SEARCH :)

3321 views / 15 in the last 7 days

2 votes | 0 in the last 7 days

Tags: mouse simulation demo with-source algorithm a* pathfinding prototype

open in greenfoot
Your browser is ignoring the <APPLET> tag.
Don't press space more than once! (I will fix it....)
Request For Comments
Keysbourne

2011/9/8

Looks good. I like the stepping through process. I implemented the A* algorithm here http://greenfootgallery.org/scenarios/1259 and have used it for a few of my games. But I like how your program steps and displays what's going on, though it is difficult to make out the numbers.
Cool, I looked at your source and generally the idea is the same, obviously not quite the same implementation, but it has the same features like open/closed list (or variable in the object itself in your case) and checking to see if we have already found the node and if we do have a lower cost to that node then making ourself the parent node. One big difference is that as I say in the description I have an object on each grid square that stores it's cost (*1 for ver/hoz movement and *sqrt(2) for diagonal) and it stores object references to each of the neighbouring nodes whereas yours just relies on counting grid positions to find it's neighbouring nodes.. As for the text, I made each grid tile 32x32 pixels so I had to make the font height 9px to fit it in, I guess I could have made the grid tiles a bit bigger instead... Anyway, all will be revealed when I release the source code soon, I just need to neaten things up a bit and add a couple extra comments :) (Oh yeah, yours was the first source code I've read in the gallery that has comments in it!)
Pretty cool.
A new version of this scenario was uploaded on Thu Sep 29 18:29:00 UTC 2011 As promised, the source code is now here. Licensed under the GPL v3 or Later. I didn't manage to make many changes, just added a couple more comments and fixed the bug if you press space twice (well in a way, I guess I could have cleared the open and closed list so you could watch it again. Yeah shoulda done that.) So now that you have the source you can see the 4 and 8 directional movement and try out all my different heuristic functions. :)
Here's the source code, as promised!
402377_2911817076873_1304015802_3183781_998552265_n_thumbDuta

2011/9/29

Very nice. Will look over the source code :)

Want to leave a comment? You must first log in.

Who likes this?

No_avatar_thumb Keys_thumb