18 replies to this topic

[diegzumillo]

Hello there,

The game I'm trying to make has some unusual functionalities and, with it, some unusual algorithms. I'm not really a programmer, (I'm a physicist, if anyone's curious) so I hope the developers in this forum could shed some light in some problems I'm facing. Also, writing about it helps me think. I'll explain in more detail what I'm doing, if anyone's willing to read it up and give some feedback I'd appreciate it

Feature #1: The game takes place in a randomly generated city. I've studied a few of the existent algorithms and decided that most of them are not suited for games, as they're too slow even for something to be generated only once at the start. So I've come up with my own, very simple, system. It's basically a grid of premade blocks, also with random elements in it. That's good enough for what I have in mind.

Streaming this big city as the player moves is not the big problem. I already have some ideas in mind. The difficulty is making it work with the next feature:

Feature #2: I need A LOT of NPCs. After several tests with the usual AI in games, I realized that even with the dumbest path finding algorithms the computational cost increases dramatically with the number of NPCs. So I decided to use a different algorithm (you can read about it here).


The algorithm can be summarized as follows: Take the whole walkable area and make it a 2d discrete grid. For simplicity, let's consider that every NPC has the same goal, a single tile in this grid. Anyway, the objective of the algorithm is to construct a vector field that defines for every point in space a vector pointing to the direction that minimizes time, distance and whatever we want to the goal tile. This way every NPC, wherever it is on the grid, knows where to move next to get to his goal.

All right! I have this implemented already. It does what it promises, the cost increases almost nothing with the number of NPCs, allowing me to get hundreds of npcs moving, creating lines and all those patterns. However, the cost increases dramatically with the area, obviously! So I have to keep it small.


Phew! you're still reading? thanks! The problem now:

This navigational grid also needs to be streamed. From my current 'guessings', the ideal size for the city blocks are a bit bigger than the maximum size I can get for the navigational grid. I'm already planning on making the whole game with a lot of fog, to facilitate these things lol. But still, I'm staggered with the problem of how to stream the city blocks AND the navigational grid. Maybe I should also break the blocks into smaller pieces, each with its own definition of navigation tiles..

Any ideas? suggestions? About anything related, really. If anyone's working with streamed big worlds, crowds, random content etc, care to share some thoughts on the subject?

[6677]

what do you mean by stream, stream is usually sending the data over the web elsewhere.
I assume you mean render

[diegzumillo]

Sorry, I'm using this term very loosely here (is loosely a word?) without regard for current conventions. But, yes, essentially to avoid rendering the whole thing and calculating unnecessary stuff. It loads adjacent blocks only,

[Ashaman73]

what do you mean by stream

Here streaming meant to load data on-the-fly while the game is running, this is common practise in most modern games.

Streaming should be done asynchronously, that is, load and prepare the data in a second thread and activate it , once the loading/postprocessing is done. Best to use some kind of cache (i.e. LRU) to hold only a meaningful number of city blocks in memory.

You should hold at least two navigation grid/map levels. The first level is a low resolution, whole game , map which connects city blocks and is always in memory. This helps if npcs needs to travel from city block to city block even when a city block is not loaded yet. The hi-resolution map will be loaded with the city block, once it has been loaded, you need to connect it with adjacent loaded city blocks, but this should not be a problem.

Edited by Ashaman73, 27 June 2012 - 04:54 AM.

[diegzumillo]

Threads? That went a little over my hobbyist head I'll see if Unity (I'm working with it) provides tools for that.

[Ashaman73]

Threads?

If you want to avoid threads, you could try to stream/post process only a little portion of the city block per frame until a whole city block has been loaded.

[diegzumillo]

Ah! I see the problem. If I load a whole block when the player crosses a line there will be a sudden drop on fps, clearly. Gently loading one thing at a time could work, but I'll see if any Unity dev has encountered this and see how they dealt with it, it's a pretty common feature.

[mark ds]

I've just had a very quick look at the paper you linked to... are you aware of AMD's Froblins demo? There would appear to be quite a few similarities.

If you haven't I suggest you check out the video (look on youtube) and the accompanying paper. Watch from about the 6:30 mark.



http://developer.amd...s/froblins.aspx

Edited by mark ds, 27 June 2012 - 05:50 AM.

[diegzumillo]

haha! I was not aware of this, thanks for pointing it out. And at page 11 we can even see the vector field, it's probably the same algorithm. Only they get to do it on the GPU, while I have to squeeze all game logic and navigation in the cpu.. I'm not nearly skilled enough to try GPU programming!

edit: it is the same algorithm. It's in their references

Edited by DiegoFloor, 27 June 2012 - 06:06 AM.

[diegzumillo]

I guess that's why they can have a much larger terrain. My limit here is 40X40. Above this limit and fps becomes unacceptable (already accounting for game logic that's still to be implemented)

[dougbinks]

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!

[diegzumillo]

Interesting. I'll take a look. Thanks!

Doesn't seem optimized for large crowds though.

[jefferytitan]

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.

[diegzumillo]

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.

[jefferytitan]

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.

[diegzumillo]

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!

[jefferytitan]

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.

[diegzumillo]

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.

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.

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?)

[jefferytitan]

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.