Archived

This topic is now archived and is closed to further replies.

BSP and pathfinding

This topic is 4945 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i''ve wrote a small 3d engine that supports Quake3 BSP maps, it works perfectly but the problem is that now i have to write the ai for the monsters. how can i make a npc (bot, monster, etc etc) move alone? what kind of pathfinding should i use?

Share this post


Link to post
Share on other sites
I suggest checking into A* using a binary heap or priority queue. With proper A* implementation you can control the tradeoff between accuracy and speed using a single variable. A* is very powerful and highly documented on a variety of sites. Here''s one to get you started:

http://theory.stanford.edu/~amitp/GameProgramming/

Share this post


Link to post
Share on other sites
i''ve already readed about the A-star.. but the problem is that i don''t think i can use any kind of tiling system ''cause the map is PURE 3D (there are planes above planes and so on).. this way i cannot create some kind of indicization and so i cannot run the A* :/

but how is made pathfinding in Q3 ?

Share this post


Link to post
Share on other sites
I have not done anything like this myself, but here are a fiew thoughts.

A binary tree can be good for short distance navigating and object avoidance. Just throw a fiew rays into the binary tree as 'fealers' from the moving object, if any ray hits a wall then the object cannot go any further than that in that direction.

However it is very difficult to path-find using a BSP, as it doesn't explicitly store any adjacency information. So using A* directly on a BSP is out of the question.

What you need is a separate structure that you can use A* on, and combine it with sort range object avoidance using BSP.

If you place place information tags within the level so that each tag is within line of site of one or more other tags, then these can form the basis of a higher level navigation structure.

Im not familiar with the BSP format, so I am assuming you can put this information somewhere in the file.

Now when you load the BSP file extract all of the tags. Fire a ray from each tag location to each other tag location through the BSP and store the visibility and distance results somewhere (like within each tag, as thats most convenient). You will probalby want to perform some checks to determine if an actor can actually travel between each tag and store that info too.

This information can now be used as the basis for A* to work from.

Find the closest tag that is within line of sight of the destination, this is the goal tag to A* towards.

Now choose a tag that is close to the actor and is visible to the actor. This is the start tag which you use to A* from.

Run your A* algorithm over the tags adjacency tables, and return a list of intermediate tags.

If you know how A* works then you should see how this is now a navigatable, shortest/safest/coolest path to the destination tag, depending on what critera you are using for determining the cost of travel between each tag.

Now each tag in this list should have line of sight to the next tag in the list.

Finally to get to the destination, your actor simply has to move to each tag in turn, and remove that tag from the list when it can see the next tag along.

When the actor has a direct line of sight to the destination, then it can head straight there.

I'll leave the problem of navigating to a visible point up to you, but it should be pretty easy to get some simple behavior up and running.



[edited by - Gleno on May 29, 2004 11:28:15 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i think on q3, the enemies just ran straight at you. on half-life, node entities are placed on the map by the mapper and are used by a* to plot a course for the enemy running node to node.

Share this post


Link to post
Share on other sites
Yeah. if I were you, I would place nodes on each corridor start/door, pre calculate the costs using pythagoreas and then use the nodes to do your pathfinding.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
i think on q3, the enemies just ran straight at you


Far from it. Quake3 uses basically the same bots as the Quake2 Gladiator Bot (they hired the developer of that to do the AI in Q3), it uses the same pathfinding routines. The BSP file is run through a tool that creates a seperate file, containing location and path finding information, and the AI uses that to navigate (and does so very well in most cases.. the AI understands doors/lifts/buttons/etc, can plot a course to take to reach a known target, etc). It doesnt rely on mappers to define well-placed waypoints, everything is done automatically by one of the compile tools (for the locations/pathfinding file)

Share this post


Link to post
Share on other sites
I have a full 3d engine, although the levels are more like 2.5 d, b/c they don''t have a lot of floors over floors.

So, what I did was use an algorithm that

a) finds the highest triangle within a small square area on every 1 square meter of the level. This creates a 2d grid with heights at each spot.

2) consolidate all grid squares into the largest rectangles you can if the have the same height. Tell each grid which rectangle id it fell into.

3) go through each grid square, and find neighboring squares with different rectangle ids. If the heights of the rectangular areas are similar ( < 2 meters ), then I count them as neighbors that you could move between

4) hook up a* to use these rectangular areas to find paths between the rectangular nodes.

The good news about this is the large rectangular areas reduce the cost of pathfinding to lower than a regular grid

The bad news is that it only tells you how to get from area to area, but not exactly how to move within an area.

Share this post


Link to post
Share on other sites
The QuakeIII Arena bot used an Area Awareness System...

Q3ABotAI_15.pdf

You can instead just use waypoints to mark locations in the world and connect those waypoints with paths. The paths are then used by A* to determine which waypoints are reachable from which other waypoints.

botman

Share this post


Link to post
Share on other sites
@botman: very good idea :D i''ll try it very soon ^_^ but i have still some problem while i try to understand how works the Area Awareness System...

Share this post


Link to post
Share on other sites