Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been writing a game in my free time, and I'm planning to add a transportation network based on a buildings demands and production. However, I'm not sure how to manage this efficiently, and most importantly with limited CPU time.

The two key issues are, how do I pair producers and consumers efficiently, and how do I route vehicles between them?

I have A* working for path finding now, but how do I alter this to include the congestion that will occur from many transports? Perhaps as each vehicle is assigned to a road, that road's cost increases some given value?

An open source project that seems to have similar features is OpenTTD. They define the problem as a Multi-commodity flow problem, but don't give many more details. The paper that describes their algorithm is no longer linked unfortunately, and I feel it may be a bit complex.

share|improve this question
    
Have you tried something so far? –  Gustavo Maciel May 13 '12 at 14:31
    
If I understand right, multi-commodity flow is used when you have already paired producers and consumers. I'm not sure how the cargodist branch of OpenTTD does it, but the source is available; have you looked through it? –  amitp May 13 '12 at 16:08
    
For A*, make the edge cost be the estimated travel time for that edge. Once you have some traffic, measure the actual time it takes for your vehicles to move along that edge, and use that as the estimate for the next time you run A*. If there have been no recent vehicles on that edge then revert to the original estimate (based on distance). –  amitp May 13 '12 at 16:10
    
@GustavoMaciel Currently A* routes vehicles between a destination and its closest source. I don't really see this solution scaling well. –  silenthunter747 May 13 '12 at 19:02
add comment

1 Answer

Short answer:

Don't!

Longer answer:

OK, you are trying to compute complex path-planning, for multiple suppliers and demands. This is presumably going to involve some kind of peon/slave or worker/robot unit. However, in the same breath, you say you've got limited CPU resources.

I'd suggest you take a note from Shamus Young and figure out what you actually want to simulate in your game, and what can be safely faked. Remember, as Shamus puts it, in videogame it doesn’t need to be right, it just needs to look right [sic]

If this is a non-violent city simulation game, I'd guess that although players may find it cool to look at the little transports for a little bit, they have other, more important things to concentrate on, which affect gameplay. In that case, you'd be well on your way if you just faked something that looked kind-of OK. For example, if I recall correctly, X-COM: Apocalypse had actual, factual path-planning for the transports which the player controlled. i.e. Their base-to-mission taxis for the little soldiers. However, the little civilian taxis, buses, and ambulances, which scurried around on the main map, did so without any real path planning. If you zoomed all the way in, and got the camera angle just so, you'd see that they spawned behind buildings, so that they weren't normally visible spawning, and they disappeared behind other buildings, so that they could just travel in straight lines, and not use up precious path-planning CPU time. To further fake it looking cool, they spawned more ambulances and fire trucks beside buildings which were on fire, and less taxis in those vicinities. So cool.

However, if the transports are indeed a central, or strategic part of your gameplay, then by all means, add proper pathing for them. The peons in Warcraft, or any number of other strategy games come to mind. If they were faked only, players could not attack enemy transports and defend their own.

You asked if you could have a cost associated with congested roads, to avoid pathing many units over them. This would probably yield good results, and as far as I know, A* and other search algorithms already have costs associated for each edge in your graph/map you're pathing through. The only thing that remains would be to increase the cost of an edge/node/whatever when a unit passes through it, or has a path that travels through it. The trick would be that its cost should be somewhat time-sensitive, so that it's not overly decongesting a road, when it doesn't need to be. For example, if transports A, B, and C all use road X, but ten seconds apart from each other, then they can all safely use it. Calculating the time at which any road/node/thing is occupied by a transport may be problematic, depending on how your pathing algorithms work.

Good luck!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.