### David joined Aug 1, 2009

Dec 2, 2013
Portugal
Male
Private Message
Members Only
##### Skype

A Path Beyond Level

11

Indie Game Developer (like the movie). I made a couple of games and I usually tweet a lot.

A* Pathfinding

For my current project I've been working with A* as a path-finding solution.

Basically it's a way to get from point A to point B.

This is used for AI in games mostly on tiled based games, It's very simple to understand and implement.

As A* traverses the graph, it follows a path of the lowest known cost, keeping a sorted priority queue of alternate path segments along the way. If, at any point, a segment of the path being traversed has a higher cost than another encountered path segment, it abandons the higher-cost path segment and traverses the lower-cost path segment instead. This process continues until the goal is reached.

The major choke point is the heuristic used to calculate which node to take next. I've started by using Manhattan Distance.
Its primary advantage is that it will generally get you to the target faster than most alternatives. Its primary drawback is that in a 8-way pathfinder so it is not guaranteed to give us the shortest possible path.

code:
float cost = 10*(abs(currentX-targetX) + abs(currentY-targetY))

Although it works fast it's not accurate and if I forced for finding the shortest possible it was rather slow for my 80x44 grid (3520 tiles), sometimes taking 3-4 seconds to find a path.

I decided to take another approach and using Diagonal Shortcut, its primary advantage is that, because it is balanced, it is able to fully consider small modifiers like a turning penalty or influence map modifier like having a non walkable tile, a rock, a tree, whatever. It is a bit slower than the Manhattan method, though.

code:
float cost;
float xDistance = abs(currentX-targetX)
float yDistance = abs(currentY-targetY)
if (xDistance > yDistance)
cost = 14*yDistance + 10*(xDistance-yDistance)
else
cost = 14*xDistance + 10*(yDistance-xDistance)

In case you are wondering the 10 and the 14 are to define if it's a diagonal or a horizontal/vertical movement since diagonals take longer to traverse than straight lines of course.
After I'm getting much faster movements.

It's not that Manhattan is worse and you shouldn't use it, it all depends on the application your using.

* On a square grid that allows 4 directions of movement, use Manhattan distance.
* On a square grid that allows 8 directions of movement, use Diagonal distance.

This is a video I've done using Manhattan distance using tile grids generated from a black and white image.

Wizardum Aug 31 2010, 5:33pm said:

wow um PortuguÊs por aqui
isto hoje em dia é dificil de encontrar

bem boa sorte para o teu projecto, segundo li, estás quase a acabá.lo.
Fico à espera ;)

cheerz

DJ_Link Sep 13 2010, 3:43pm replied:

Heheh thanks.
Só vi agora aqui o comment. Pensava que o indieDB alertava. É difícil fazer track a isto tudo.
Sim está mesmo quase o jogo. Vamos lá a ver.

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Groups
Indie Devs Hobbies & Interests group with 979 members
Spotlight Official group with 471 members
Desura Official group with 9,779 members
DIYGamer - An indie group for indie news. Entertainment & Press group with 116 members
Different Pixel Developer with 2 members
Friends
INtense! friends since Mar 22, 2012
LotusGames friends since Jul 26, 2010
dcfedor friends since Sep 5, 2012
jax42 friends since May 22, 2013
paranoidMonkey friends since Jun 20, 2010
jtpup0 friends since Sep 13, 2012
Wizardum friends since Sep 13, 2010
StefanRomanHosch friends since Apr 10, 2012
m0r3n4 friends since Jul 1, 2010
KopanoGS friends since Oct 24, 2012
Statistics
414
5,158 of 417,529
0 members
1 day
66
2,928
2,196 (3 today)