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

Automating Level imports from Blender to Godot

  Recently I've been making some levels in Blender an importing them into Godot. There are only about 7 or 8 shaders for each level, not counting dynamic objects which will be added later. But to improve rendering performance, it can be a good idea to split the meshes up into sections. At that point you might be faced with a list like this: Or it might be even more chaotic, if you didn't use simple names for the objects in your level. So it can take a long time to sort out all the meshes, make them unique and add textures and so on. Blender imports with simple Blender textures, or with placeholder materials. This is sometimes OK, but if your Godot shaders are very different to those used by Blender, it means applying new materials to every mesh object in the level when you import the scene. I found that during the design process, I was importing and readying a level several times before I was happy with the final layout. So at first I was wasting a lot of time. In Blender, I us
3 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

Make your game models POP with fake rim lighting.

I was watching one of my son's cartoons today and I noticed they models were using serious amounts of simulated rim lighting . Even though it wasn't a dark scene where you'd usually see such an effect, the result was actually quite effective. The white edge highlighting and ambient occluded creases give a kind of high contrast that is similar to, but different from traditional comic book ink work. I'll be honest, I don't know if there's a specific term for this effect in 3d design, since my major at university was in traditional art. I learned it as part of photography. You can find plenty of tutorials on "what is rim lighting" for photography. It basically means putting your main sources of light behind your subject so that they are lit around the edges. It can produce very arresting photographs, either with an obvious effect when used on a dark subject ... ..,or as part of a fully lit scene to add some subtle highlights. See ho
Post a Comment
Read more