[casual_games] Pathfinding

[Jules Robichaud Gagnon]

A* is in my view the best path finding algorithm you could use but like you
said the movement may be unnatural in a non-tile based game. You could use
the output nodes of the path finding to create Bezier Curves or other
interpolation technique to create a smooth movement when changing direction.


Flocking algorithm could also be used to avoid other objects and customers.
I used this in a game so the creatures will avoid wall. I added a 4th
technique to force them to avoid objects at all costs.
http://opensteer.sourceforge.net/ 
It is in C++ but the main idea is very simple and can be done in any
language. My own implementation of flocking was in Java.

________________________________

Jules Robichaud Gagnon

Directeur R&D
Wendigo Studios Inc.
496 St-Marthe, Chicoutimi, Qc, G7J 3C8
Cell : 418-550-7596
Sans Frais / Toll free : 1-888-WENDIGO (936-3446) #707 
Fax : 432-577-6694
www.wendigostudios.com 
 
-----Message d'origine-----
De : casual_games-bounces at igda.org [mailto:casual_games-bounces at igda.org] De
la part de Dimitrios Bendilas - ZEFXIS
Envoyé : 30 août 2007 14:22
À : IGDA Casual Games SIG Mailing List
Objet : [casual_games] Pathfinding

Hello everyone,

I hope this post is not very off-topic.
I have a programming question which I hope someone will be able to shed some

light on.

We are building a click-management game. Its core mechanics resemble Diner 
Dash's.
We are trying to implement a pathfinding algorithm that makes sure our 
heroine does not
pass through "tables" (they are not tables actually, but similar concrete 
objects).

The main difference from Diner Dash in regards to pathfinding is that the 
tables in our game
are spread in the screen in a much more random manner. Our heroine has to 
avoid tables
and walk around them to go to the customers, who are located around the 
tables.
The game is not isometric and it's not tile-based. It's like most 
click-management games,
having a side-top "camera" view and some pseudo-perspective.

We are trying to figure out which is the best pathfinding approach here.
We tried A*, but the algorithm makes the sprite move in a zig-zag pattern
too much and the movement seems very unnatural.

Does anyone know what is a good approach for the pathfinding in such games?
Maybe someone that has developed a similar game can give us a hint?

Thanks a lot!
Dimitrios

-----------------
Dimitrios Bendilas
Game Designer/Lead Developer
Total Eclipse Games
www.totaleclipsegames.com


_______________________________________________
Casual_Games mailing list
Casual_Games at igda.org
http://www.igda.org/casual-subscribe
Archive: http://www.igda.org/casual-subscribe
Archive Search:
http://www.google.com/coop/cse?cx=010373383720242846960%3Az3tdwggxil8
List FAQ:
http://www.igda.org/wiki/index.php/Casual_Games_SIG/Casual_Games_List_FAQ