Skip to main content

The basics of A Star Pathfinding

Someone wanted to know how the code works for basic A* path-finding.

Rather than reply in Facebook, I've made a quick post for it here.

1. create an array of nodes to represent your level. 

It can be nodes with connections, or it can be a list of co-ordinates where connections are assumed to be NESW where a node exists.
 
Example 1:
 
level = {"001":[["002", 5.0], ["003", 5.0]],
"002":[["001", 5.0], ["003", 5.0]],
"003":[["002", 5.0], ["001", 5.0]]} 
 
This is a dictionary based "mesh" type array, for easy reading. You can see it has 3 nodes arranged in a triangle. Each node is connected to two others, and in this case, the distance between each is 5.0 units. 
 
It's easy to see how this mesh could be expanded. You just need more points. Each point must include its two neighbors and the distance between them. 

 Example 2:
 
level = [[0,1,1,0],
[0,0,1,1],
[1,1,1,0],
[1,0,0,0]]
 
This is an grid based array arranged as a list of lists, for quick access and fast performance. It would look like this:
 
XOOX
XXOO
OOOX
OXXX
 
The Os are walkable, the Xs are not.
 
2. Get a start point and an end point.
 We'll use the second array for our example.
Start is [0,1] end is [3,0]:
 
XSOX
XXOO
OOOX
EXXX
 
3. Run an algorithm for every tile... 
until you find the end or until you run out of tiles to search (if there's no valid path).
 
You need to keep track of the tiles you have checked and the tiles still to check.
On each tile, check the distance to the goal, and the number of tiles traveled from the start. Add these two numbers together and store them along with the tile information in your "checked" list. Next check the neighbors of that tile. And so on.
When you find the goal go back through your "checked" list one by one until you get to the start. This is your path, though you now have to reverse it.
 
What it looks like:
 
XS4X
XX35
434X
EXXX
 
You can see that the tiles which make up our path have the lowest values, because the distance back to base, and the distance to the goal are nearly equal. If your method of getting the distance to the goal is correct, then you will always find the shortest path.
 
4. Give this info to the agent.
If the map isn't going to change, and you don't care about bumping into other agents, you can just have the agent run through the path to the end.
Otherwise, you have to run this code every time the agent moves, and get a new path (which might be the same as the old path).
 
NOTE:
A quick (dumb) alternative.
have your agent check every square next to them.
get their distance to the goal. Immediately move to this new tile and add the tile to a list of visited tiles.
The agent then repeats the task, checking neighbors and moving. Don't check any tiles in the "visited tiles" list. The distance from the start is always zero. So only the distance to goal is important. The "visited tiles" list stops them going in circles when the distance to goal is the same in neighboring tiles.
If you get stuck, for example, all neighboring tiles are on the "visited tiles" list, clear the list and start over.
Monsters using this algorithm will walk around endlessly if they can't find the goal. And the path is probably not going to be the shortest path available. But it is a very simple code and very fast to run. Great if you have a swarm of dumb enemies.
 
 

Labels:

Comments

Post a Comment

Popular posts from this blog

Advice needed on tilesets...

I need some advice on which is the best way to handle building the dungeon. Right now I'm using prefabs for my dungeon, they have a north south east and west section for each "room": The basic tileset. This has several advantages, and also several disadvantages. Firstly I can have curved rooms, I can have tunnels and other interesting shapes. The tilesets can look quite nice with a little work. On the other hand I can't easily get the navigation data before building the map and once the map has been built I can't make changes to the layout, like having active pit traps or believable secret doors. Although the rooms are interesting, they are quite repetitive, and it takes a lot of effort to make even a few different variations. Also rooms are constrained to one size. A newer version of the tileset with a lot of variant parts for making more interesting rooms. To create a tile set is a real headache too. Planning how to lay out the UVs, trying to cra...
7 comments
Read more

Upstairs / Downstairs.

I've decided to make my prefabs multilevel. Later this should allow me to add pit traps and other great stuff. It also makes it easier to line up stairs so that you can exit them on the same co-ordinates where you entered them. The prefab editor is pretty much finished, it just needs some code for loading up prefabs from a saved dictionary, so that they can be checked or edited. The entries will need to be forwards compatible, so I'll be loading each tile and then translating the indexes to a new array, that way if I add extra indexes or extra info (like traps or puzzles) I'll be able to update existing prefabs to work with the new standard. Click for a video.
6 comments
Read more

Video Diary 8

Things are moving along well, there's been a lot of progress on the action manager side of things. Actions have finally moved to the UI, so you can initiate actions by clicking the appropriate button. I've set up some dummy actions to show what happens visually when actions are taken, but the actual dice rolls and such are yet to be integrated. The UI objects are also being added, though some are non functional or empty at the moment. Click on the image to see this week's development video. Every time I add something big I also add about a dozen small things. Like the selection box visualization. Previously this was using render.drawline, and old fashioned Blender function which can be impossible to see at certain resolutions, or at certain frequencies. I replaced it with a function that adds planes of the right size and scale in the right location. I also made all characters a little bigger. I still need to do some work with vectors and final target locations t...
3 comments
Read more