Hi there, I am in the very beginning of thinking about a small game like DungeonSiege, but just 2D Top Down. I have some programming experience but not with games. I read some articles about A* path finding and also saw some demos of it. Maybe I got it wrong, but those demos all looked tile based, like a check board/matrix. Maybe I did not understand everything but with those matrix it doesn't seem to be possible to move freely and have arbitrary barricades, is it? I think of units with different sizes. So you might have passages with are to narrow for huger units. Another thing is that I want to be free with the level design. So that I can draw a barricade at any place with any angle I want. The units should also be able to move freely. I think of having polygons marking static impassible areas and bounding boxes for the current units moving around. Or should I divide the whole map (passable/impassible areas) into polygons? So what data structure you would use? Would be nice if you could point me to according articles. Rgds tmg

Hi tmg,

As you noted, many pathfinding examples use grid based graphs because of their simplicity. You can approximate any map using a grid, not just tile based maps. Unfortunately, an accurate approximation requires very dense grid, which leads to inefficient pathfinding. Alternatively, you can use a quadtree to represent your map. It's much more efficient, but still only approximates arbitrary geometry.

Polygonal graphs provide an accurate representation for arbitrary surfaces. That requires you to divide the whole map into convex polygons, e.g. triangles. There are lots of algorithms available for that purpose. You can either use the polygons as graph nodes and connect adjacent polygons, or use the edges between the polygons as nodes.

There are also other types of graphs, such as visibility graph (I prefer the name corner graph, as it has generally nothing to do with visibility) and a graph based on manually placed waypoints. Google for "pathfinding graph representation" to find out more. You can use A* with any type of directed graph.

Dealing with various sizes of units is an interesting problem. You can "expand" the geometry (obstacles etc) to create a graph that matches a single sized units. If you can divide your units into few groups, for example small, medium and large units, you might want to generate separate graph for each group. On the other hand, some representations can deal with various sizes of units. Grid based graphs can prevent large units from moving to tiles near to obstacles, which eliminates narrow passages. Corner graphs can actually compute a maximum size for each connection, but you probably won't need anything that complex.

Hope that helps,

-Jarmo