A question about complexity and algorithms

Getting Started
1

Hi! I have a kind-of far-away dream to learn game making and make a game about transit planning. However, I’m afraid that what I’m imagining might kill a normal PC because of its complexity, which would be a big bummer after investing all the time and energy to learn. So I’d appreciate advice about the limits of complexity, specifically about pathfinding/shortest route.

Basically, my game idea is that the player is creating a train/transit network, and entice commuters to switch from commuting by car to commuting by train. This happens when the travel time from the passenger to his desired destination is shorter by using the route available by train rather than by road.

Obviously there would be many possible routes from passenger to destination, so I imagine dijkstra or A* is the way to go - each station being a node and every rail track between stations being a segment, with the travel time being the cost. The same logic would apply to roads for the car routes… The passenger calculates shortest route in the road graph and compares it to shortest route in the train graph.

Now, my problem is that I’m hoping to have a rather realistic size of the playing field, say 100x100km or so. With careful planning, the road network(which I imagine is the most complex of the two) could have around 10,000 nodes. Potentially, there could be 40,000 passengers, each with their own desired destination.

So is there any way that 40,000 passengers, in real time, can evaluate the cost of using the road system vs the train system? Basically the game would need to perform 40,000 shortest routes calculations for the 10,000 node road graph, and 40,000 shortest route calculations for the 1,000-5,000 node train graph.

Keep in mind it’s only simple numbers we are talking about, none of this would be represented graphically. I’m only worried about what this amount of calculations would do to a regular gamers computer.

Hope what I’m asking is clear, otherwise please ask me to clarify… very grateful for any input!

2

I don’t think this would be a problem. You said real-time… in real time, there aren’t that many passengers deciding which way to go at once. Probably only a handful, and each one could spend seconds pondering their decision.

In addition, there are lots of ways to reduce the complexity of the problem, such is hierarchical pathfinding, which is a pretty good model of how real humans do it. If we’re visiting a restaurant the next town over (and not using a map app on our phone!), we don’t plan every turn from the get-go. Instead, we think: how do I get from here to Neighborville? Well I can take I-10 or I can take Coast Highway, which is a little longer but prettier. This is a very easy route to plan because there are only a couple of options at this level. I pick the highway. OK, now how do I get from where I am to Coast Highway? That’s a much simpler problem. And once I get to Neighborville, then I consider how to get from the highway exit to the restaurant, which is also a reduced problem.

So… go for it. This is totally doable.

1 Like
3

The key trick to remember with path finding is that it doesn’t all have to be done at once. Finding 40,000 routes every frame will kill you. But you only need to find each route once, then that route doesn’t get changed until it’s travelled.

You can also do it backwards, and find travel times per station/highway. This might actually be cheaper, especially if a lot of agents are following the same basic route.

1 Like
4

Thank you for your replies! It seems you both agree some sort of clever shortcuts are needed to trim down the number of calculations - that’s what I figured. Even though computers are good at math I still kind of could see my suggested numbers were just too large. Out of interest, does anyone know any examples of games where complexity of pathfinding lies in the upper range of what is tolerable? It would be good to know where I can set my limits for my thinking.

5

Hmm, that’s not really what I was saying at all. I was saying not to worry about it. If you find that clever tricks are needed, then there are many available. So you can worry about it then — for now, get on with your simulation!

2 Likes
6

The simplest solution is always the best. That means you don’t need to come up with a clever system that optimizes simulations for you until you recognize performance is a problem. But it also means you don’t need to actually simulate everything when an approximation of that simulation will suffice for your purposes.

Joe has a lot of experience with simulations, so you should consider what he says very thoughtfully.

1 Like
7

I’m reminded a bit of Neo and Morpheus’s exchange: "You’re saying I can dodge bullets? -“I’m saying you won’t need to”(to paraphrase badly). My original question was really asking for limits on performance - can a regular computer take on calculations of a certain(probably too high) complexity. Joe’s answer is basically saying “you wouldn’t be doing that anyway, so no need to worry about it”. Am I understanding that right?

The way I’m sketching the game does still comes up with requirements for some fairly complex calculations, if is was to work the way I wanted it to. Mainly, I WOULD like all my passengers to have phones that tell them the best commute, since that is how people work in real life these days. Thus hiearchical pathfinding scares me a bit as it could miss unexpected travel possibilites(I live in a city with exceptionally developed public transport, and sometimes Google Maps finds me some very interesting and time-saving, and counter-intuitive, routes!)

So while I definitely don’t want to scoff at experience(IE I recognize that the best solution is probably to rethink and replan my game mechanics to be more about approximations and so on, like you say), I am still very curious what kind of complexity a regular computer can handle, if it ends up being required to deliver precisely the game experience I want to achieve. I haven’t found any layman-friendly information about this so far, after googling quite a bit.

If we assume that the pathfinding calculations doesn’t have to be done in real time, but rather as a one-time event when the transit network is rebuilt in some way, would that be more reasonable? I wouldn’t mind a load screen for a second or two while the commuters figure out their new routes.

Based on some trimming of my concept, I now envision (max) 10,000 pathfinding operations on unique graphs that on average would only contain a few hundred nodes. Is that crazy, or is it actually something a computer could solve in a second?

Very thankful for people’s experiences!

8

Well, the dirty secret is that Google Maps is doing hierarchical pathfinding too. The route it gives you may not always be the optimal one — but it’s highly likely to be, because usually there really are only a couple of reasonable ways to travel between cities.

I think you’ve also missed the very key point that your passengers are all pathfinding at the same time. They do it at the start of their route, which takes a couple of seconds, and then they spend many minutes (or hours?) following that route before they need to do it again. (Probably much longer, because they went somewhere to actually do something, not to immediately go somewhere else, right?) 3 seconds out of (e.g.) 6 hours is 0.0139%, so that’s how many of your travelers are path-finding at any one time.

I didn’t say that. Nobody in this thread has said that. In fact we said the opposite of that. We told you to quit worrying about it and get on with your simulation, because any performance problems you might run into can be easily fixed later.

That would make things much worse. Probably still something you can cope with, but details will depend on exactly how the transit network was changed, how much notice the commuters are given ahead of time, etc.

If you have only a few hundred nodes, you could simply store a completely solved network that eliminates the need for pathfinding at all. (You need only to know the trip distance from every node to every other node, which is an NxN table, 4 bytes per entry; that’s about 350k for 300 nodes.)

So again I say, don’t worry about it. I think you are looking for excuses not to do this project, but you’re not going to find any here! :slight_smile:

9

You could try Aron Granberg’s A* pathfinding: A* Pathfinding Project

Free version has quite a lot features; you could use point graphs at least for trains, and perhaps for cars too, and grid graphs for pedestrians if you need more precise pathfinding. One great thing is node penalties (think traffic jam, accident) that is missing from Unitys’s pahtfinding. There’s many example scenes too.

Read optimization from his documentation, there is some general tips too: A* Pathfinding Project