Automatic navigation meshes

[AF]

There is no value in mentioning that engine xyz does not have the problem or case of local steering if your not going to name the engine or even the genre. I have a game engine and it doesn't feature this problem, its in my backyard but you cant see or touch it, you have to trust me.

[aegis]

it's easy enough to find xenoargh.

argh, any heat in front of the actor will help prevent congestion, as other units will be less likely to walk exactly there, however big. check out the crowd continuum video for an example of how awesome it can be.

he does have a point of it possibly scaling to unit size. I'm not sure how the implementation handles the map exactly, so I don't know how much larger unit sizes would benefit from much wider heat projections.

[Argh]

I'm familiar with the idea.

You do know I proposed and described what is now called heatmapping in a discussion with k-man and jcnossen several years ago, yes?

I got the idea from an article about using fluid dynamics to produce ideal traffic flow. The engineer was talking about slowing all traffic to a median speed to decrease behaviors that lead to turbulence (aka traffic jams). I started to imagine it in 2D as a pixel flow and made some pictures. IDK whether that stuff is still available or not. K-man thought it was cute, but that's as far as it went at the time

Anyhow, what I'd like to propose would work considerably better, in terms of real-world efficiency.

I've done some napkin-math, and I'm certain now. If I explain in detail the how and why, will this go anywhere useful, or am I wasting my time on this issue again?

I don't really care if we finally try out heat-mapping, I think it's great that we're finally going to do something about congestion and more importantly about local steering... but I brought this up in the first place because:

A. I tested it early, and found it created some of the problems that have been brought up here, in terms of behavior. What jK's pointed out in terms of bugs are probably to blame for the worst of it, but there are other issues, and I'm not really feeling like wasting my time explaining the other stuff that will probably not work right- let's say that the issue is prediction and leave it at that.

B. It's sloooow. Too many sectors need to be examined to do it well- that's one part of the prediction problem that will be obvious when we deploy it. And there are all those sector updates as well, which aren't trivial. There are better ways.

[AF]

Not at all I would say that the A* algorithm itself is more of the problem performance wise

[jK]

Heatmapping won't ever make pathfinding faster, it slows down it a bit.
Also it won't fix any issues, where the current pathfinding fails (e.g. setting `too long` waypoints on factories). The only reason for heatmapping is the crowd optimization.

Also that crowd continuum would be ways to complicated (and so too slow) for Spring. But saving a direction (and so speed) for each heatpos might be an useful addition. Atm it already saves an 'owner' tag for each heatpos, which can be dropped then, so the memory usage wouldn't increase that much.

[Argh]

And there are problems with topology not being scaled correctly (i.e., a pixel may represent vastly different real area) and other issues.

Again, I'm glad that imbaczek and the rest of you have spent time on this, it's certainly better than nothing. I do want to see it working without bugs. But I have had time to look around at other things, and I am pretty sure a better solution exists, and navigation meshes are part of it.

I will try and find time to talk in detail about what I have in my head later. I have most of what I think will be a very efficient strategy that's specifically aimed at the problems of an RTS, but it will take a couple of hours to write the explanations / illustrations (some of it is fairly novel, some of it just needs detailed justification) and I don't have that time atm.

[hoijui]

best thing would be, if the pathfinder would be really easy exchangeable. I am thinking on having an IPathFinder class as single engine<->pathFinder interface. then Argh could eg implement his ideas, instead of describing them. i got told it is already fairly separated, but last time i looked at it, it seemed to be still some more webbed into the engine (eg, access of public member vars).

[aegis]

that crowd continuum would be ways to complicated (and so too slow) for Spring

but not for supcom?

[AF]

I was thinking such a change would be best myself Hoijui, do you dare to christen libPath?

( Argh if you cant describe the gist of it within 250 words, then go into detail afterwards, then you've failed and no amount of clarification and detail will unveil your work from the confusion. More volume does not necessarily mean more value. )

[Argh]

If you want the precis, here you go, I think I kept it under 250 words.

1. The approach provides topologically accurate summaries of 3D travel surface data, created by both automatic systems and hand-tweaked artisan materials.

2. The approach provides for local and global steering, traffic flow control, and some UI control processes to enhance the user experience.

3. The approach requires fewer updates than heatmapping, provides for much faster search performance for ideal paths than A* at the cost of some memory overhead, and will be very efficient for most cases because of various savings.

4. The approach provides fast solutions for mass movements and other common problems that defeat traditional approaches.

5. The approach provides for topological change, but is optimized for static topology.

6. The approach can be used in a variety of settings other than RTS games, such as traffic simulation, FPS AI, and other areas.

[hoijui]

sounds like a marketing agenda. i guess technical description is what most in here would prefer.

[Argh]

Descriptions of the logic, some explorations of methods to optimize certain areas and pseudocode await some free time on my part, as some elements are somewhat novel and I do not feel an incomplete description would be appropriate.

[zwzsg]

Was "the approach" already used with success in other games, or is it something you invented?

[AF]

Descrilbe in a gist how it works, at a high level, then use that to garner our interest for the minutae details and specifics

[Argh]

Was "the approach" already used with success in other games, or is it something you invented?

Some of the ideas have been used in many major games.

Navigation meshes aren't exactly novel- they're used in a lot of engines.

Some of the concepts for local steering aren't novel- they've been used in a wide variety of settings.

The novel stuff is applying some of these things to problems that are specific to a RTS or other large-scale engines, but some of the subsections would be of interest to FPS designers wanting to create better behaviors as well.

[EDIT]Watched the crowd-continuum video. What I'm talking about will work considerably better and with a far lower cost, and it mainly showed me what I already knew, which is that the costs of heatmapping won't overcome the disadvantages. Note how much more poorly it worked in the four-corners exercise.[/EDIT]

[aegis]

considerably better at a far lower cost? you saw how well it worked in realtime with the epic amount of troops running around?
is your overall idea tested and proven?

and you realize four corners is a pretty hard thing to optimize... they pointed out how the crowd continuum model is much better than A* at four corners (road engineers solved it with a roundabout, and iirc that's what crowd continuum does)
are you sure your magical (untested?) idea will be any better at four corners?

[Argh]

is your overall idea tested and proven?

It wouldn't be actually novel then, would it?

are you sure your magical (untested?) idea will be any better at four corners?

Absolutely yes. The emergent behaviors would be considerably better for most agents in the system, and the local behaviors would be very acceptable.

While I'm talking about this in rough terms... do a thought experiment, and tell me what happens to the four-corners problem if agents of different sizes and velocities get involved, and the implications for a heatmap scanning approach in terms of CPU use.

[aegis]

not proven

absolutely yes, works well

:/

and a heatmap lookup can be near linear complexity, depending on how you choose your next location after seeing you should avoid an area...

[Argh]

OK, let's try another tack, since you seem to have some imagination problems.

How many checks do you have to perform to do an adequate job, if the agent gets larger?

How many checks do you have to perform, as the agent's velocity increases?

How many heatmap squares must be updated, in both cases?

How many trigonometric steps are involved to determine which sectors to check?

[Pxtl]

OK, let's try another tack, since you seem to have some imagination problems.

And you wonder why you end up in so many flamewars.