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

Latest Media

We're sorry, but no images, videos or audio files have been added to this gallery.

If you would like to share media with the community, sign up and you can.

Blog RSS Feed Report abuse Latest Blog: A* Pathfinding

0 comments by DJ_Link on Oct 28th, 2010

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.

Groups
2 Girls 1 Game

2 Girls 1 Game

Hobbies & Interests group with 78 members, open to all members

Join us every week for our definitive one-stop podcast to quench your thirst for outstanding independent games. From clever old school 8-bit freebies...

Desura

Desura

Official group with 10,084 members, open to all members

Desura is a community driven digital distribution service for gamers, putting the best games, mods and downloadable content from developers at gamers...

Different Pixel

Different Pixel

Developer with 2 members, invitation only

Different Pixel is an indie game studio formed by one programmer and one designer. Our main goal is to create games using creativity and art in a way...

DIYGamer - An indie group for indie news.

DIYGamer - An indie group for indie news.

Entertainment & Press group with 117 members, open to all members

This is the official Desura group for the indie game blog/community DIYGamer.com. Feel free to link up with other readers, speak about any and all indie...

Indie Devs

Indie Devs

Hobbies & Interests group with 1,098 members, open to all members

A group dedicated to indie and standalone game development.

Spotlight

Spotlight

Official group with 530 members, open to all members

Each month we bring to you new and old (updated) game and mod playthroughs, trailers and weekly recaps covering the mod and indie gaming scene, so sit...

Post comment Comments
Wizardum
Wizardum Aug 31 2010, 5:33pm says:

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

+1 vote     reply to comment
DJ_Link
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.

+1 vote     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Level
Avatar
Avatar
Offline Since
Sep 19, 2014
Country
Portugal Portugal
Gender
Male
Member Watch
Track this member
Accolades
Desura Spotlight
Statistics
Activity Points
428
Rank
5,606 of 471,664
Watchers
0 members
Time Online
1 day
Comments
67
Site Visits
3,054
Profile Visitors
2,775 (1 today)
Contact
Homepage
David-amador.com
Private Message
Send Now
Email
Members Only
Steam
^DJ_Link^
XBox Live
Different Link
Skype
the.david.amador
Twitter

Latest tweets from @dj_link

RT @Lunarsong: Found Quest of Dungeons on #Android by @DJ_Link today. Really fun game, totally worth it if you like Roguelikes! :) https://

3hours 17mins ago

@MichaelAdaixo thanks, will do :)

3hours 18mins ago

After several hours of flight delays I finally arrived at London T.co

3hours 49mins ago

@rogeriopvl @hsousa sounds like a well spent time at geek room ahaha

Sep 22 2014, 7:09pm

@rogeriopvl cool, there's always space for tequila :P

Sep 22 2014, 5:54pm

@rogeriopvl México? Bring me a hat ahahaah

Sep 22 2014, 5:51pm

@rogeriopvl no. dude, wherever you are, stay there, seriously

Sep 22 2014, 5:21pm

RT @Teddy2029: So I just died on my longest play through of Quest of Dungeons. I think I died a bit on the inside as well ;_;

Sep 22 2014, 4:11pm

RT @grumpygamer: Screw it, I'm just going to get a new email address. That's easier.

Sep 22 2014, 2:57pm

RT @grumpygamer: Slowly working through several hundred unanswered emails. Where is a hard server crash when you need one.

Sep 22 2014, 2:57pm

INtense!
INtense! friends since Mar 22, 2012
StefanRomanHosch
StefanRomanHosch friends since Apr 10, 2012
MartinCaine
MartinCaine friends since Jul 27, 2010
paranoidMonkey
paranoidMonkey friends since Jun 20, 2010
jtpup0
jtpup0 friends since Sep 13, 2012
Wizardum
Wizardum friends since Sep 13, 2010
J.S.B
J.S.B friends since Apr 5, 2014
jax42
jax42 friends since May 22, 2013
KopanoGS
KopanoGS friends since Oct 24, 2012
LotusGames
LotusGames friends since Jul 26, 2010