That looks awesome; dynamic just doesn't do it justice. Pathfinding is likely going to be a nightmare. Do you have a website? I'd like to keep tabs on the project.

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.

The picture helps alot.

Issues:


Will movement over the irregularly places 'rubble' blocks be allowed
(also their irregular placement likely rules out a simple grid mechanism)

The constructs allow muliple levels (over lapping path surfaces), so
a navmesh like system will be needed.

The constructs are 3D so a 'ceiling' height check must be done for movements.

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


Looks more and more like true collision testing for the pathfinding.
The large open areas will help streamline alot of movement (use a 'coarse' grid
with preference for moving thru grid squares with no blocks in them and then resorting to a more complex/costly 'fine' local pathfinding only when needed.


Sidelight:

Your rebuilding (Grab) mechanism might make for an interesting posting (how you manipulate the blocks to where yoy want them (6 degree of freedom is hard to do)

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'....

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

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