Probably not the first time that this is asked here, but... 2 (A*) pathfinding questions. - Following the path In my map editor I place nodes that are connected with each other. When I calculate a path, I get a listing of node coordinates and how to reach them (walk, crouch, swim, etc.). But I don't want my agents to exactly follow these coordinates. They should cheat by taking a shortcut on the nodes, if possible. I calculate the open radius around each node, so I could use that info to shift the path a little bit. But I was wondering how other shooter games are doing it. Maybe I got it wrong, but are games like F.E.A.R. creating a 'polygon' path? Instead of exact coordinates, a list of polygons (made of the path nodes) is created and the player can move inside these polygons. - Dynamic objects Navigating through a static world is 'easy'. But how do shooter games deal with (large) dynamic objects such as cars or a metal desk? My dumb brute-force enemies might try to kick away those objects. But the smarter or weaker ones should dodge. I could block the relations between nodes. But that means each (bigger) object that moves, should check which node(s) it is blocking. And if one object leaves a node, it could still be blocked by another object. Don't know, but I guess its quite hard to maintain this. I could also pre-define it. It won't be correct anymore when the situation changes (all tables and chairs are blasted through the room), but the chance is relative small. However, IF it happens the agents cannot use the space that was previously used by big objects, and will collide with the replaced objects. Another trick I could think of is by trial and error. When almost colliding, we turn 90 degrees left or right and keep walking until the path towards the target is open again. This works for rectangular objects and humans. Although agents with a large rotation curve (cars) should look further forward. So far, this is the best solution I could think of. But maybe I'm missing some other tricks... Greetings, Rick

In the past I've used a waypoint map for global navigation between areas and a combination of ray-casting and fuzzy-logic for local navigation within areas. An area is any convex location which *should* have a clear path across it (ie a room with two doors). This technique is useful for avoiding other characters as well as dynamic objects, and also helps to keep the characters away from the walls (so less 'wall-hugging').

Most of my 'areas' are open as well, meaning you could travel from one portal to another without being blocked by (static) geometry. But there's always the exception of course. Some areas have height differences and stairs. How do you deal with those? In my case some of the enemies can swim or climb walls/ceilings as well...

But if I understand you right, you dodge objects/pillars by looking a little bit forward with raycasting? That comes at a cost, but since I don't have dozens of (active) enemies, this is certainly worth trying.

Greetings

Quote:

Original post by spek But if I understand you right, you dodge objects/pillars by looking a little bit forward with raycasting? That comes at a cost, but since I don't have dozens of (active) enemies, this is certainly worth trying.

Sure it costs, but if it's only local to the camera it's not so bad, and it looks great. If you can get the raycasting onto the GPU it's practically free.
Stairs, water etc are more of a problem...

Depends how complex it needs to be!

A simple version could involve each node having a radius within which the agent decides that it has reached the node; adjusting the radii and the turn speeds of the agents can get a bit annoying though. A minor improvement would be to change the point-in-circle test to be a point-plane test, with the plane origin being the node centre and the normal being the reverse of the previous link direction, so the node is reached when the agent has run past the node (this works well if the agent can be moved involuntarily, or takes a shortcut - it doesn't have to run back to the node to continue the route)

Many games now use a special navigation mesh, often a simplified version of the floor geometry. Use A* to get a path between polygons, listing which edges were traversed. Then a relaxation pass which finds optimal locations on the polygon edges to minimise distance and/or angle between nodes.

In a previous game, I found the 2d bounding box of any big dynamic obstacles in the area, blocked any nodes totally covered by it, and inserted extra nodes into the A* graph which were points extruded from the corners of the objects 2d bounding box.

As SimonHx said, raycasting to find obstacles and steer around them before the agent actually runs into them is a good idea :)

Most of the famous "steering behaviors" do just that. They look at where a moving object will be some time from now, then apply force to get there, and they use raycasting to probe the space in front of them (or a box in front of them) in order to steer clear of obstacles.

Then forward collision detection it will be! I think I just put a sphere/cylinder or box x meters forward and check collisions. It doesn't matter if its not 100% correct. We humans make mistakes as well. Besides, the enemies in my game will be quite dumb in fact, not super trained soldiers :)

That "navigation mesh" wingman_j is talking about sounds interesting. Especially because I don't have to put probes everywhere. I did something similiar a few years ago as well, but with the very same mesh as the normal world, which is not always a good idea (polygons intersected by others, to close to the walls, etc.). Mapping a floor(or wall/ceiling) mesh in my favourite modeller is faster than spraying nodes. But I need to find a way to set additional info. Some passages require a special animation (jump over a wall, crouch, and so on). And some polygons require special abilities (swimming, climbing stairs, ...). Well I think I can work that out.

I suppose that 'relaxation pass' is to prevent agents walking through walls or move unnatural. Can you explain that a little bit more in detail, or maybe someone can point me an article/demo?

Thanks!
Rick

You can tag polygons in max/maya/whatever to trigger animations or gameplay effects (ice, damage etc). The type of poly can also be used to adjust the heuristic cost of traversal.

The relaxation pass is mostly for aethetic reasons. A route between polygons tends to end up quite jagged even for a straight line, because you're finding a path between the centre points (or edges if you do it that way). So you then find the edges traversed, and slide the crossing points along the edges to make a nice smooth trajectory.

If there is no adjacent navigation poly, walking over a bridge for example, then the crossing points should be constrained to be no closer to the end points of the edge than the agent's radius - otherwise they tend to fall off :)