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

Blog RSS Feed Report abuse 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.

Report abuse What are your target platforms for games?

0 comments by DJ_Link on Jul 26th, 2010

Hi there,

Out of curiosity I decided to make a poll about that platforms do you develop for.
I think it should be interesting.

You can vote here:
Twtpoll.com

On some other news related to me, well, progress on my port to IPhone/IPad is going well and you can read more about that here => Indiedb.com

I'll try to update this more often.

Report abuse Presenting myself to IndieDB community

2 comments by DJ_Link on Jun 18th, 2010

Hello everyone. My name is David Amador.
I am an Indie game developer. Indie...I really like this word, don't ask me way. Maybe cause it sounds cool on my mother language, I'm from Portugal btw.

A couple days ago I launched my first Indie game, Vizati, it's not a very big game, nor mega original but we tried to polish it the best we could.
It's on sale on GamersGate and Impulse Driven, check for more info on our official website Differentpixel.com

Different Pixel is our trademark for releasing games from now on. We are team of two. Myself as a programmer and Rita as a designer/graphic artist. The game took us around 3 months to make. I started the engine around a month earlier.

We decided to make this small game to test our skills, although we have some ideas of bigger games we felt like it was to soon to embark on a 8+months development. It's would be better to start with something smaller and so Vizati was born. We have the game running on PC, XBOX360 and Windows Phone 7

So I just wanted to present myself and say hi to all developers out there. I hope to hear stuff from you and exchange ideas with.

PS: I have a blog here

Level
Avatar
Avatar
Offline Since
Dec 23, 2014
Country
Portugal Portugal
Gender
Male
Member Watch
Track this member
Blog Statistics
Articles
3
Views
49
Views Today
0