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 :)

12067 views / 26 in the last 7 days

2 votes | 0 in the last 7 days

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