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

RSS My Blogs

A* Pathfinding

DJ_Link Blog

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.

Start a group Groups
Indie Gamers

Indie Gamers

1,469 members Hobbies & Interests

For fans of indie games and hardcore indie gamers, no matter at all whether these indies are commercial or freeware/opensource! This is a hub used for...

Indie Devs

Indie Devs

1,579 members Hobbies & Interests

A group dedicated to indie and standalone game development.

Desura

Desura

10,142 members Entertainment & Press

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

Spotlight

Spotlight

597 members Official

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...

DIYGamer - An indie group for indie news.

DIYGamer - An indie group for indie news.

50 members Entertainment & Press

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...

Different Pixel

Different Pixel

2 members Developer

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...

2 Girls 1 Game

2 Girls 1 Game

87 members Hobbies & Interests

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...

Comments
Wizardum
Wizardum

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

Reply Good karma Bad karma+1 vote
DJ_Link Creator
DJ_Link

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.

Reply Good karma+1 vote
moddlord1
moddlord1

yes okay.

Reply Good karma Bad karma+1 vote
Post a comment
Sign in or join with:

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.

Level
Avatar
Avatar
Last Online
Country
Portugal Portugal
Gender
Male
Friends
Become friends
Member watch
Follow
DesuraSpotlight
Statistics
Rank
7,306 of 646,244
Visitors
4,821 (2 today)
Time Online
1 day
Activity Points
435
Comments
66
Site visits
3,065
Contact
Contact
Send Message
Homepage
David-amador.com
Steam
^DJ_Link^
XBox Live
Different Link
Skype
the.david.amador
Twitter

Latest tweets from @dj_link

Interesting to see so many games releasing for Switch in December, usually a time devs tend to avoid right?

19hours ago

RT @Effyneber: Announcing a new beta version of Veldrid, an advanced 3D graphics library for .NET. It uses Vulkan, D3D11, and Open… T.co

19hours ago

Found this interesting, what does it take to code a GameBoy game in 2017? Gamasutra.com

21hours ago

I don't know why but I always find a bit weird to have pixel art games with fonts that are way more on the "round s… T.co

23hours ago

Oh no #NetNeutrality Theverge.com

Dec 14 2017

And the Simpsons did it again. What if the creators invented a time machine and are only using it to mess with us? T.co

Dec 14 2017

Just seen Star Wars :) I can get back to the internet now

Dec 14 2017

RT @ALWyvern: @DJ_Link Annual Alien releases on the way, Ripley now a Disney Princess 🤣

Dec 14 2017

I have faith that Disney will take better care of the Alien franchise

Dec 14 2017

Disney is buying Fox for $52billions :O

Dec 14 2017

Friends
INtense!
INtense! Online
ChrisIDN
ChrisIDN Online
overlordror
overlordror Online
paranoidMonkey
paranoidMonkey Online
jacobpeltola
jacobpeltola Online
Roman_indiedb
Roman_indiedb Online
MartinCaine
MartinCaine Online
dcfedor
dcfedor Online
Wizardum
Wizardum Online
KopanoGS Online