I know all about A* and other path finding algorithms. I was wondering if anyone can guess how the pathing in an rpg like Baldurs Gate should be done? The backgrounds were pre-renered and they used polygons as borders so the characters didnt walk right through the buildings. But I was wondering how the path finding was done? Did they have grid? What were the nodes and weights in such a case?

You don''t need a grid to use pathfinding algorithms. The nodes can be positioned anywhere. The edges connecting the nodes represent the cost to travel between each node. This cost may be something as simple as the distance between two nodes, or it may also reflect other factors such as the cost to travel across certain terrain or up/down gradients. This structure, of nodes and connecting edges, is called a graph .

I don''t know for sure (because I''ve never played the game), but I suspect the nodes in Baldur''s gate were positoned by hand, probably by the artists/level designers.

My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Thanx for the reply that sounds like a viable option. Since the backgrounds were prerendered I guess they had a graph that represente all the walkable surface area.

Having played a lot of BG, I can tell you that the pathfinding was rather average. It often went the wrong way to get to the goal and got stuck, which suggests that paths were planned ''on the fly'' over several iterations of the main engine loop and that an initial guess (or start of path from first iteration) was used to get started (which would then sometimes lead to a dead end).

Further evidence of ''on the fly'' planning were NPCs that would stop and think about where they were going when they reached an obstacle.

As to how path planning is done in such games in general, there was an excellent article published at Gamasutra on the topic. Check the archives there.

Timkin

Thanx I will. I am guessing that the pathing is done in a similar fashion in Diablo as well?

I cant seem to find that article on gamasutra.com. I found 2 paragraphs about a type of map setup buts thats it. Can anyone point me to it please?

[edited by - wolfbane on July 22, 2003 10:05:16 AM]

quote:

---

Original post by Timkin
Having played a lot of BG, I can tell you that the pathfinding was rather average. It often went the wrong way to get to the goal and got stuck, which suggests that paths were planned ''on the fly'' over several iterations of the main engine loop and that an initial guess (or start of path from first iteration) was used to get started (which would then sometimes lead to a dead end).

Further evidence of ''on the fly'' planning were NPCs that would stop and think about where they were going when they reached an obstacle.

---

It failed to take into account the motion of friendly units (if a friendly unit was blocking the way, it would attempt to walk around it, even if both friendly units were ultimately destined for the same place). Also, it stopped the characters walking when you clicked on a new destination, which was annoying as 9 times out of 10 the new destination was in the same direction as the old one. Yes... their pathfinding could have done with a lot of improvement. (In fact, I am left wondering if there is anything of high quality in that game except the artwork )



[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]