Maybe this though I'd be surprised if you can get it running fast enough (assuming your agents have a reasonable amount of movement freedom). You will need some way of calculating/estimating the ability to traverse path segments (a) that's going to involve a lot of collision checks and (b) you probably have to assume that movement of your agent won't change the environment - e.g. when it walks over a delicately balanced set of blocks. And you'd have to redo your pathfinding every time the relevant part (and you don't know what that is!) of the environment changes.

This would definitely work in non-realtime, including letting your agent do rocket jumps etc. Maybe it's possible to combine it with local steering - i.e. when your agent wants to go from A to B it:

1. First starts walking in a straight line from A to B, negotiating obstacles using some local steering.

2. At the same time you simulate the agent's movement (distributing this over multiple updates... but still running much faster than real-time) in order to estimate his position in the future.

3. If you detect that the agent will eventually get stuck, then start the RRT pathfinding from that (predicted) location. With luck, you'll have calculated the result by the time the agent actually gets there (may be 10-20 seconds into the future). With even move luck, your agent will actually end up in the same place that you started your pathfinding from!

4. Assuming everything worked, when your agent reaches the stuck location, have him play a "puzzled" animation (!) then follow your RRT path to B, assuming one exists.

They say that a picture tells a thousand words. Those two completely clarified the problem you are facing. Thanks! 8)

Given the highly deformable nature of the game world, it is not realistic to use a map in which to do pathfinding, since you'd (a) need to create it again after every change to the world; and, (b) find it very difficult (computationally) to compute a connectivity map for each agent (I'll assume that some agents can climb over things that others cant). Hence, you need to use the world itself as your map, which means reactive planning and automatic control systems.

If I were you, I'd break this problem down into at least two parts. The first is designing a controller for a spider (or other type of) agent that can move freely around the world, climbing over things that are low enough (which includes stairs) and avoiding things that it cannot climb over (walls, high obstacles). Given a direction to travel in the controller should either cause the spider to move in that direction or return a failure state (because the path is blocked). If it has to climb over obstacles, it should do so. I have some suggestions for how you could do a simple spider without needing to do a full robotic simulation. If you're interested, I'll post them later.

Above this level you'll want a reactive architecture. You could work with, as a first order approach, a steering system. However, this would not take into account planning.

You will want to do some form of abstract planning based on the assumption that the world remains static. It should be simple and low cost though, since these plans will often be invalidated by the actions of players (usually when they work out what the spider is up to and try to prevent it). I would recommend using a fixed set of 'canned plans' and selecting the most appropriate given the state of the world, or the actions of the players.

The end result of building such a system would be one that deals in abstract, non-absolute terms at its highest levels and in very simple movement terms at its lowest levels. This is not a trivial problem though (as I'm sure you're aware).

Cheers,

Timkin

Looking at it, I think you're going to need to use an octree for coarse node based route planning, with quick checks for empty nodes. You can take the octree method as low down as you want, or adopt steering behavior at a low level.

I'd recommend you adapt the route node octree when 'static' collidable geometry starts moving or being changed, and again when it comes to rest. For everything else I'd simply use standard 'bump and go' collision detection and steering.

Edit: As an optimisation, I'd cache known routes within nodes - you can then spend idle time calculating and caching routes between various nodes to allow smarter behaviour as time goes on, and have 'fast and dirty' solving (causing 'narrow' paths to be skipped as they're too low down the octree) to keep things moving. Given the complexity of the problem field, I probably wouldn't have routing knowledge tied to individual AI entities.

Ultimape: Our game & company is called "ROBLOX" and our website is at http://www.roblox.com. It's kindof a mess right now, but we are getting a web dev soon to make it nice. There is an alpha-test client you can DL and play with.

Timkin: I would love to hear about your robotic spider controller ideas. Before I can do anything, we need support for scriptable motors. Once that is in, I was going to attempt an "open loop" robotic spider that moves based on scripted leg coordination. It seems like this should be good enough to catch the occassional player who is out in the open. I think a "closed loop" controller would be very hard to make work, especially using lua (our embedded scripting language).

I didn't realize the scope of the online aspect of it. It's almost like secondlife, only with legos. How much data does it typically take for an average sized area?

It looks like each area is saved and uploaded to your servers for other people to download, perhaps when you save you could also implement some precaclulated pathing then. Of course it would be invalidated upon using the world, but it could be a good place to start with when considering dynamic repathing.

You could perhaps rasterize oddly placed blocks down to the grid...
so a shape like

.........____....\...\....\___\.  ........would be considered:.........._____.....|_...|_.....|____|...........

in terms of it's path blocking properties.
asuming you work with a grid.

AP:

Quote:

I think I see ladders (navmesh special case..)

Actually right now we are able to solve the ladders the same way we do stairs - with the character controller :-) Like you say, this makes all our "walkability" queries very expensive.

Quote:

The wreckage shown looks like it would take 100 times as long to put backj together than it did to blow up (hope thats not what one rocket will do in your game or it will degenerate quickly into 'fighting in ruins'....

Our eventual goal is to allow people to import pre-built models into the world, so brick-by-brick construction will only happen once (and we have a different tool for doing that that looks alot like a CAD program)

Quote:

Hmm Maybe you will have to keep those Spiderbots busy repairing your scenery !!!!!

Right now it autoregens, but we would like to have janitor-bots constantly running around and fixing things :-)

I'll try and post something on my spider bot controller thoughts this week. Lots to do at work... hopefully I can find time during the evening.

Cheers,

Timkin

I had originally thought that the answer to your spider controllers would be to define walking and climbing controllers for them and then switch between the two depending on the existance of discontinuities in the local gradient surface around the spider. However, the climbing controller complexity is quite high because of the number of degrees of freedom in the spider (each leg would need two hinge points... times 8 legs... cut that in half by using some symmetry arguments and constraints for imposed balance). The walking controller is much easier since you can use a state machine for each leg and a cockroach walking model: the lead legs define the motion and each other leg's action depends on the state of a set of coupled legs.

I think that a better solution might be to observe the local height map around the spider and compute a local tiling based on the projection of surfaces into the floor plane. Then, for each tile, determine a cost as a linear function of gradient, with gradients that are too steep to climb up having infinite cost. This reflects the change in horizontal velocity as slope increases. Connectivity between tiles would be determined by the height discontinuity in the original 3D surface (also reflected as a slope discontinuity between tiles). If the height discontinuity exceeds an upper threshold, the step up is too high for the spider to climb. If it is negatively signed, the spider could jump down. Then, perform local pathfinding on a horizon determined by the size of the local heightmap. I would think that using something like MILP (Mixed Integer Linear Programming) would be a good, fast approach, since fast solvers already exist. Alternatively, write your own local planner. You'll need to determine a cost heuristic for the horizon edge, but a good idea might be to favour higher positions rather than lower ones, since it's easier (and cheaper) to climb down to get to the goal than up. Thus, the spider would tend to take paths up and over obstacles, but that are not straight lines (but rather represent shallow climbs), much like how roads are built over mountains.

As for animating the movement, you can either define a single walking animation and rotate the base of this walking frame to the local surface gradient, or define a coarse set of animations based on the slope. You would need to work out how to smoothly transition between animations as slope changes, especially at discontinuities. This might be tricky, but ultimately, should prove computationally cheaper than trying to compute the movement of each leg of the spider and its body and doing collision detection with its feet and the surface.

I hope this helps. If you want me to elaborate on any of these ideas, please holler.

Cheers,

Timkin

I've had a similar problem (I'm making an RTS game). Now I'm dealing with group behavours, not with path finding. Try this which worked for me:

1) Find the path from the point you're to the dst. I assume that you're ussing a queue of positions once you've obtained a path.
2) Each frame compute the possibility of crashing if you make a new step.
3) If you'll crash, use A* to concatenate the point where you are to the point from the queue (and not the final position)

Step 2 may sound very expensive, but it is not, at least the code i've written is pretty fast (I don't do magic though)
But it works.