You should take a look at Recast and Detour: http://code.google.com/p/recastnavigation/, blog from Mikko (the developer) here: http://digestingduck.blogspot.com/

Mikko's a professional games developer who developed and released Recast and Detour in his spare time, under a permissive license. Both are in use by AAA games, and support crowds and streaming as per your requirements. Good luck!

Interesting. I'll take a look. Thanks!

Doesn't seem optimized for large crowds though.

You chose an interesting problem to look at. Does the number of people in the crowd have any effect, or only the area? Just wondering whether it would help if you could in the distance have "trains" of people, e.g. 10 low poly people in a line moved and animated together.

As far as streaming chunks of city, definitely a good plan. How would you manage people moving between chunks? I'm wondering whether individuals would be recognisable enough that you could tell if they were destroyed if you went away then came back.

Another possibility is to move only the ones you can see at a high refresh rate. You could update the rest less often but at a higher velocity, e.g. 4 times as fast every 4 frames. Or if the crowd is a uniform density skip the vector fields for out-of-sight people altogether by just saying that each person takes the place of the person in front of him/her (and fall back to vectors if two people pick the same target).

Just a few random thoughts. Let me know if I'm off-base.

You chose an interesting problem to look at. Does the number of people in the crowd have any effect, or only the area? Just wondering whether it would help if you could in the distance have "trains" of people, e.g. 10 low poly people in a line moved and animated together.

As far as streaming chunks of city, definitely a good plan. How would you manage people moving between chunks? I'm wondering whether individuals would be recognisable enough that you could tell if they were destroyed if you went away then came back.

Another possibility is to move only the ones you can see at a high refresh rate. You could update the rest less often but at a higher velocity, e.g. 4 times as fast every 4 frames. Or if the crowd is a uniform density skip the vector fields for out-of-sight people altogether by just saying that each person takes the place of the person in front of him/her (and fall back to vectors if two people pick the same target).

Just a few random thoughts. Let me know if I'm off-base.

Hi jefferytitan, thanks for sharing your thoughts!

The number of people does influence the calculation time because it has to generate a density map on the grid, but it really is neglectable. I couldn't find a superior limit because I ran out of room on the grid to put everyone, so that's a good thing. The size of this grid is the big problem (I think it was N log N, with N being the number of points) and the best I can get is smaller than a city block, more or less.

With that in mind, it's unthinkable to use this navigation type on the whole city. At least for my humble project, we settled for local movement of people only and cover whatever lies beyond this navigational grid with fog. A cheap solution, but we need to work within our capabilities, and it doesn't compromise this particular project

There is however some accountability for global configuration and movement of NPCs throughout the whole city, the chunks, as you said. My idea in't complicated, but I'm not sure if will work (I'm not sure if anything will work at this point lol). I'm thinking about generating a basic population density on the city, that is, associate a number of NPCs in each block. This way I can easily create a distribution like a gaussian centered in the urban part or any other shape. So when the player reaches a block, I use this number to generate the NPCs, and I can also reduce/change this number based on the actions of the player there etc.

Movement through the blocks with this density system is possible, but I have to think in terms of a density wave instead of individual movement.

I'm really frustrated right now. With this navigation system only possible in small scales, close to the player, I wonder if it's worth it. The goals of the NPCs will always have to be on the border of the grid, just to simulate casual NPCs passing by.

I think I found the appropriate paper and I've had a quick breeze through the algorithm, but can't say I have gotten the details. Can you explain why it scales N log N, and what N is in this case (e.g. control vectors, block length, block area)? It looked like the main movement loop was just "for each agent convert their position to parametric, move them, convert back to world space", so I'm not sure how the block size is relevant. Unless you're changing your control vectors?

As far as your frustration, it all depends upon your goal. Do you want the crowd movement to be realistic? Plausible? Convincing enough to the user? It's a sad truth that most game "AI" is smoke and mirrors. It's only a problem if the player spots something is wrong. Often simulation quality is sacrificed except for near the player. If you want more plausible NPCs, one approach is this:
http://aigamedev.com/premium/interview/alibi-generation/
You can probably find a non-pay version somewhere. It's essentially about making NPCs that wander without purpose, but fabricate a purpose if watched by the player.

N is the number of points used in the grid. The relation to the area appears because the distance between each point needs to be approximately the radius of each NPC, to get a reasonable resolution. I have no idea how they calculated N log N, though! I just believe their analysis

The main loop runs through every point of the grid. First, constructing what they call the 'cost' field, then constructing the 'phi' field (solving the eikonal equation) and then constructing grad phi. It has to run through all the points more than once, actually.

Realism is not really a concern. I would gladly switch to another algorithm, if it can handle a whole bunch of npc! That's the only demand hehehe Right now I'm trying to find that article you linked!

Wow, it turns out I missed your link and was looking at a totally different algorithm:
http://www2.mae.cuhk.edu.hk/~cwang/pubs/CGAInteractiveCrowd.pdf

It seems to have less smarts, although looks pretty quick.

With the method you're using you could perhaps put some performance enhancements in, e.g. skip calculating cells with nobody in them (which may happen with very small cells), use something more agent based on low-density areas, etc.

I'll take a closer look to this article, it might give some ideas. It does seem to apply the same basic idea of calculating fields over the whole area.

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]With the method you're using you could perhaps put some performance enhancements in, e.g. skip calculating cells with nobody in them (which may happen with very small cells), use something more agent based on low-density areas, etc. [/background]

[/font][/quote]

It might be possible! The field can be calculated until all NPC grid points have been accounted for, as the rest isn't necessary (could this make the fps unstable?)

I'm not sure whether it would. But from how you describe it, I imagine that at least 70% of all cells would be empty at all times, so I think there would be a degree of statistical consistency to it.