next »

[digitalgibs]

This post may be too generic, but I do have a couple specific questions.  I am thinking about prototyping an RTS game, but there are a couple of algorithms that I am unfamiliar with.

1) What would be the best networking design for an RTS similar to C&C4 or Starcraft II?  An FPS style server-client doesn't sound very friendly for 100+ units running around.  I thought about using some kind of lock-step, but that seems so old-school.  Is that still how people are handling RTS, even with broadband?

2) Have there been any advancements in path planning for RTS units?  Starcraft II looks pretty amazing, and Supreme Commander looks to have settled on something pretty nice too.

3) Any suggestions for rendering large groups of low polygon units, without using the latest and greatest video card features?  I'm thinking about aiming for net-books as the target platform.

[Guillaume]

1) I don't have too much experience with that, but I could think of some ticks to get around the massive overhead that would be generated by moving around 100+ units- for example, if they're organized in squadrons, just move the squadron around (ie. in the Total War series). And of course you're going to want to only update the units that have actually moved (by comparing the last sent gamestate to the one currently in memory), potentially sending another "keyframe" every few seconds. You can definitely get inspired by video codecs for that kind of stuff.

2) The algorithm used are always pretty much the same- variations from Ford-Bellman's, Warshall's, Dijkstra's algorithms, A*, etc. Of course they have to be adapted to your type of obstacles, and so on.

3) You might want to look at techniques such as geometry instancing. However if you aim to make it run on every device known to man, it'll be tricky- my microwave doesn't support OpenGL extensions However sometimes it's worth sacrificing a tiny bit of your audience for that kind of performance and development gains; iirc geometry instancing is supported only by DX9+ cards, so that wouldn't be a solution that requires too much sacrifice. Your judgement.

[bateleur]

Best network architecture depends on your requirements.

Generally it's fine to just send actions to other clients (whether via a server or using UDP) and let each client process all actions. So instead of each unit sending its position every frame, it only sends data corresponding to events like "new target", "created", "destroyed", "activate monocle" and so on.

The only time this is a problem is if you need to make the game resistant to people trying to cheat, but that's extremely difficult to do anyway.

You also need to be a bit careful with handling dropped connections. Orders packets from each client need to be delivered per frame (or similar) even if there are no new orders so that you can tell if one of the clients has connection trouble.

[shrimp]

Regarding pathfinding, A* (or whatever you use to plot a route from A to B) is the easy part.
All these algorithms are designed for finding a route through a field a static obstacles (or more abstractly, a static node network).

If your units don't block pathfinding, for example if they are human soliders and the smallest gap between obstacles is large then your problems are greatly reduced. However this is fairly unlikely.

Imagine you implement A* and allow each tank to request paths individually from the pathing system.

If you send a single tank from A to B, no problem, it will look great.

In a more realistic but still simple example, you might have a group of 5 tanks at point A on one side of an open plain and you send them to point B at the other side. In this case, all the tanks will request paths (problem 1: high bursts of load on the PF system) from their current position to point B (problem 2: they can't all exactly get to B, they need to be arrayed sensibly around B) and they all set off. Problem 3 is that naively they will perceive each other as obstacles to route around. This leads to some stupid looking wiggly paths that are immediately even more stupid because the tank they were pathing around has also started moving, and has almost certainly moving into the path of another tank.

Problem 4 is that other unrelated units could be moving across the path, invalidating it to some degree. So maybe you should periodically repath? In fact, you definitely should, but you still need to solve Problem 3 as it will keep coming up each time you get a new path.

That's the simple case. If your map is more like a set of corridors (like a city) then corridors can be blocked by packs of units. Clearly if these units are static then A* will just give you the "next best" corridor if there is one. However, if they are moving then maybe they'll have gone by the time you get there.

Bonus problem: Units might have different abilities to cross rivers, crush obstacles, etc, so you have to design the navigation data to allow this.

So, yeah, have fun!  

I have implemented some AI to handle this in the past, but it was far from perfect, so I won't tell you what game it was  

IMO the main things are:
- if units are moving as a group, have some system to group them into squads/convoys for the duration of the movement. Ignore squad mates when pathing, only the "leader" requests a path, but make sure you consider the group when choosing a path (e.g. don't choose a route that some members can't do, or maybe split the group if needed)
- implement (or find a 3rd party implementation of) some reactive steering to follow the path and divert round minor obstacles and other units (see this)
- somehow give units a way to advertise to the pathing system what they are doing, so that other units can make a sensible choice about whether to go around them or their future position, or ignore them.
- design the underlying data with all these problems in mind, e.g. a tile/node on the grid knows what is currently blocking it

I haven't really studied recent RTSs for this stuff, but maybe I'll take a look at some later.
Hopefully it gives you some idea of the scope of the problem:
                                                             

(Oh, final bonus problem: If the unit is sent to attack something, you can just give the target unit's position as the destination of the path, but that will often end up looking stupid for long-range units in obstacle-heavy areas. You might want to do some clever analyse of good attack positions for a given target, or just make the player solve it with micromanagement)

edit: Useful links: http://www.cgf-ai.com/links.html

[Sos]

C&C pathfinding is cpu-devouring crap. e.g. if you send 156 units to a destinations (e.g. enemy base) it needs to calculate path of each one also calculating collision with other units in real-time and responses to the collisions, which leads to frogleaps and "I forgot where i go" movement.

My solution is: group the units and have one tight path for them. regroup only at tight passages. this will let you gain some fps, and also you will get rid of the hourglass scatter effect when passing a bridge with loads of units, since they would have to group after passing.

@3: Instancing won't clear your way to netbooks. Vertex arrays and MinGW are your friends.

Why MinGW?
Answer is simple:

Code:

char **foo = char *foo[20] = char foo[20][20] // correct for bothvc and gcc
char foo[20][20] = char foo[400] // vc would crash when accessing 20+ member of pointer array, which is pretty bad.

now to the point.
Have an array of meshes, like

Code:

float meshes[256][768][3]; // 256 meshes of 768 vertices (256 tris)
// this gives you 64k triangles

MinGW aligns arrays correctly, as opposed to storing arrays of pointers like vc does, so you can actually pass &meshes to vertex array.

Quick transform / rotate.
You will need two arrays, one is for translating, so it holds the x/y/z position for each mesh. The other array is precalculated mesh rotate lookup array for i.e. 360 degrees, so it holds a mesh in different rotate (also animation frame), so:

Code:

float lookup[16][360][768][3]; // 16 frames of 360 degrees of 256 triangles precalculated meshes.
float positions[256][3]; // positions of meshes
int state[256][2]; // [0] is frame, [1] is angle;

And have quick memcpy functions to move stuff for you.

Code:

void gimme_cannon_fodder_NAO_and_display_too()
{
  int c;
  for(c=0;c<256;c++)
     memcpy(&meshes[c],lookup[state[c][0]][state[c][1]],(768*3)*sizeof(float));
  glVertexPointer(3, GL_FLOAT, 0, meshes);
  glDrawArrays(GL_TRIANGLES, 0,256*768);
}

Here you go! Your mass cannon fodder drawing algorithm for netbooks.

[digitalgibs]

Thanks guys.  This gives me a lot to think about... Sounds like mass-sized path finding is still a big problem for games.

I did read somewhere that Supreme Commander was using something called "flow-field path finding" but the only flow-field algorithms I know/heard of are for fluid simulations and steering.  I've never seen anything talking about using it as a replacement for A*.

[Sam]

There is actually an active thread about multi-agent pathfinding.

In that thread I mention generating a heat map and having the individual agents follow that.  I'd imagine a flow field solution would be very similar, but explicitly storing "to get from here to X, go in direction T" at each point in the field.  Of course that's only really useful if you have lots of agents all wanting to get to X.

I could imagine it being used in a more subtle way: Define several checkpoint positions in the world.  Generate a flow field for each checkpoint.  Each flow field would be such that an agent can be placed anywhere on it and by just following the flow vector at their current position they will end up taking the shortest route to that flow field's checkpoint.  Then when an agent wants to get somewhere, it does something smart to find which checkpoint it should head to, then when it's near enough to its target it switches to a personal pathfinding technique.  That would rely on not needing to regenerate the flow fields too often.

Using a flow field instead of a heat map is probably better in general, as I think in the event of a map change you could update just a section of a flow field?  I'm unsure of that.  Might play around with it tomorrow.

Utterly no idea if any of that is related to Supreme Commander's stuff.  From my playing that game for half an hour, all the maps seem to be vast open landscape anyway.

[John Nesky]

Heat maps worked well for me when I made Peak. All of the code for Peak is over at wonderfl. Here's an example of an in-progress version of the game showing the heatmap explicitly.

Basically there were many many active entities in this game and it would be way too expensive to calculate paths for all of them, especially in the Flash virtual machine. However there's only three kinds of entities, and they just want to chase each other, so I built just one heatmap for each species, and every entity can just pick the appropriate heatmap to follow depending on which species it wants to chase.

And I've got some crazy hacks in there to optimize the maintenance of the heatmap by propagating changes in alternating directions...

EDIT: In the in-progress version, the blue heatmap represents the distance to the nearest green dot. Sometimes one of the green dots will survive the initial slaughter and you can watch the blue heightmap more closely.

[digitalgibs]

FYI, I found a couple interesting videos and whitepapers on flow field path finding.

http://g4tv.com/videos/44462/Supreme-Commander-2-Flowfield-Pathfinding-Trailer/
http://grail.cs.washington.edu/projects/crowd-flows/

I JUST found these, so it's all still Greek to me, but I'll be reading through these at some point.

[Dathgale]

1) What would be the best networking design for an RTS similar to C&C4 or Starcraft II?  An FPS style server-client doesn't sound very friendly for 100+ units running around.  I thought about using some kind of lock-step, but that seems so old-school.  Is that still how people are handling RTS, even with broadband?

RTS games like the ones you mentioned use peer-to-peer lockstep. Basically, all the computers involved start with their copy of the game in a known state, like loaded from a map. On intervals, each computer sends the input from its user to every other computer in the game, and they calculate the result.

[Pencerkoff]

Hello this is Pencerkoff

"flow-field path finding"

It's really cool to hear that this actually exists somewhere in an RTS.  I was trying to do this few months back and found that I didn't have the programming bravado to pull off anything efficient.

(see this)

This was great to look through, though none of the code seemed easy to get.

It still bothers me that RTS games have been around for 15 years or whatever and I still can't really make one of my own, even if it were crappy.

-PENCERKOFF

[shrimp]

FYI, I found a couple interesting videos and whitepapers on flow field path finding.

http://g4tv.com/videos/44462/Supreme-Commander-2-Flowfield-Pathfinding-Trailer/
http://grail.cs.washington.edu/projects/crowd-flows/

I JUST found these, so it's all still Greek to me, but I'll be reading through these at some point.

Those are very cool, thanks for sharing!
Take the SupCom2 video with a pinch of salt as they are comparing there system with the worst possible naive system, rather than the nearest competitor, but it's a very powerful example of good vs bad.

The academic video is really fascinating. The most striking part was the 4-way crossing with the comparision between Reynold's "boids" and their method. The pedestrain simulation wias great too. I was really expecting that evacuated building to explode or something

[Rob Lach]

I was really expecting that evacuated building to explode or something

Me too, but you know academics 

[skyy]

I'm currently working on AI stuff too and naturally went through this thread and after a while ran into this :



Mind bending... Shows the path-finding in SC2. Pretty cool stuff. I like how the "swarm" of enemies seems to stay "alive" when it stops. Pretty cool.

[digitalgibs]

That is gorgeous!

[Radnom]

Would it be too computationally expensive to calculate the path once for one of the units, then have the rest of them sort of follow him relative to where they were when you said "move", and simply steer along the path?

[shrimp]

That Starcraft2 zerg stuff is indeed lovely... really insectile, probably quite effective on people with a phobia of real insects

Funnily most of the stuff that makes it look like an insect swarm (milling around, jittering) is *exactly* the stuff I once spent weeks eliminating from a system for human characters :D

@Radnom - Yeah that's pretty much what I meant with the squad/convoy thing. Once you do that though you still have to have the non-leading members of the convoy avoid other units, walls, etc, unless you work around those problems in the gameplay design.

[skyy]

"flowfield path finding system"... eh? Looks cool anyway!





This kind of stuff crushes my soul. So awesome.

That Starcraft2 zerg stuff is indeed lovely... really insectile, probably quite effective on people with a phobia of real insects

Funnily enough, I was showing one of my AI module teachers the clip and she went crazy. "I CAN FEEL THE BUGS AROUND ME!". Instead of telling me some random bits of information on how they might have implemented it or just generally commenting on it, she went crazy and started flailing around and left. Bit of comical relief added there but that's basically how it went...


Ok, got a question for everybody. Generally for AI people but I'll throw it in here. What do you guys think of multithreading the games AI system? Obviously since all platforms are getting more and more cores/cpu's on board, you "should" start threading stuff to take load of the one cpu and this way take more advantage of the actual hardware. So, what about threading the whole AI system?

I'm working on my AI project for my AI module in university and I have completely threaded the AI in it. Basically all the entities/agents make requests to the AI manager. Like "calculate a path from here to there", "tell me about this", "can I haz cheezeburgar?" and "how many noms?".

The AI manager marks down a task from it. Thread pools activate, chern down the tasks and let the agent know that the task is done and the agent can retrieve the results. Was a painful experience to setup and to debug the start of it but works like a wonder now. So, what do you think, should people start multithreading AI? I'm generally in favour of multithreading because the hardware supports it.

[Theotherguy]

Flowfield (gradient descent) is actually a much more primitive algorithm than any of the graph algorithms (wavefront, A*, Dijkstra's, etc.) it is an incomplete algorithm -- that is, it is very possible for units to get stuck in a position where they cannot get to the goal even when a path exists, while all the others are complete and sometimes provably optimal.

The major advantage of flowfield is that it is very fast. This is why its useful for games.

Another type of algorithm you might want to consider is a visibility graph algorithm. If you represent all your obstacles as polygons (and it should be, if its a game), you can draw lines from your actor to every visible vertex, and from all those verticies to all other visible verticies from those, and so on, until you reach the goal. You then follow this graph to the goal. Your unit will find the provably shortest path through the space. The major advantage of this is that the visibility graph is much sparser than a graph based on a grid, and computing the shortest path is thus much less computationally intensive. There is a lot of overhead in generating the graph, however, so you could precompute it for static obstacles beforehand.

[digitalgibs]

I've actually implemented an area-based navigation system with local steering for simple avoidance.  I used it in Zombpocalypse to get complex zombie swarms.  That worked well enough for fast moving swarms that have a life expectancy of 10 seconds , but RTS navigation poses some interesting problems since each unit is expected to move intelligently, and without swinging back and forth, like steering tends to do at high speeds.

I've thought about using that navigation mesh path finder for an RTS.  It might not be too bad if I make some assumptions.  It seems to be the same assumptions that Starcraft II is making.

1) Unit's can pass through each other.
2) Intersecting units apply a "discomfort" to each other, and push away.  This is similar to a spring-based physics simulation.
3) Moving units have higher "push" priority, causing lanes to briefly form for a unit that is barreling through a crowd.

The main drawback is that large "areas" (or polygons) on the navigation mesh allows for a very low amount of accuracy.  If a group of units are parked on that one polygon, it's impossible to have the granular knowledge of their exact surface area that is consumed.  That is what makes grid-based so nice; the granularity is small and more defined.

But if we assume that moving units can burrow a path through a crowd, then it doesn't really matter if the path is blocked.