Videos show path finding inherently "broken"

[GenXisT 127]

I knew there would be server issues on launch and I was willing to put up with that. But reading this thread, and seeing that even the underlying ENGINE and gameplay are a mess too - that's really sad  

This stuff sounds so fundamental and wide reaching, I'm not entirely confident it will get fixed.

 

 

They HAVE to fix it... otherwise Maxis will fold.  This will end them.  People won't even blame EA anymore.

That's a programmatic error, not a marketing, launch or DRM issue.

If they can't program a game, then what's the point of being a gaming company?

[Djohaal 121]

The problem is, their whole agent-based approach scales terribly. That is a fact for every agent based game. Look at Dwarf Fortress for instance, or dungeon keeper/startopia when you got too many peeps. In a game which is natively x32 and single threaded I can hardly see performance scaling well enough to support cities much bigger than their current state or smarter agents.

 

Glassbox would be a fabulous engine for simulating a small town (ressurect sims ville?), a medieval village/feud, a mars base, or an anthill. A city, not so much.

[eburress 267]

 

IIRC fromt he GDC glasbox videos the agents use a modified A* pathfinding that searches the shortest route to the closest possible "need" for that agent.

 

What's disappointing is that the paths could be weighted based on traffic density so that shortest route isn't just the only criteria.

 

Further, Maxis once stated that agents would start out with the intention to travel the shortest route but would update their path finding based on new data such as alternative routes on roads that can support higher density traffic.  What's shown in the videos is clearly not the case.

 

I can't get it. how did Monte Cristo have managed to do so on Cities XL (and must say in an incredible way) and Maxis did not? is it that complicated?

 

There are a LOT of things about Cities XL that are superior to this new SimCity.  Imagine if Monte Cristo had the resources at Maxis' disposal...

[snick25 384]

Wow. This is just terrible. A simulation game that can't even determine paths correctly?

 

I said I felt pity for Maxis in another thread, seeing how many aspects of this game were obviously influenced by the Big Brother, but this is just unacceptable. How could they not see this?

 

My pity is waning...

[Ardandy 28]

The new patch from yesterday (1.3) seems to have helped. My 250k city is moving free-er now.

[Big Goldenski 3]

Why didn't they come up with bus routes? At least, they could have copied them from Cities XL? It works great in XL.

[Sunfighter 186]

The new patch from yesterday (1.3) seems to have helped. My 250k city is moving free-er now.

 

What they are not telling you is they reduced the number of agents by about a quarter traffic wise. If you have any cities you havent touched since that patch, watch your number of jobs and shoppers drop..yet demand stays equal..so they reduced the agents.

[john2218 8]

Yeah I had a city with 90K people and only 8000 were workers...  Dont think they reduced the number of shoppers though, still had bad traffic in the commercial areas and there seemed to be millions of shoppers all over the place.

[Nielsen 10]

Maxis should outsource this task to the NAM team. Really, it's sad that Maxis doesn't watch and learn.

[madhatter106 3,924]

Aren't problems like these what the $19.99 "Streets and Rails" addon that you just know will be coming will allegedly remedy?

 

Bingo.

 

Basically, the pathfinding algorithm is like:

 

1- Find the shortest possible route.

2- Ignore all other options and variables.

 

3 - Allow people to "fix" the game algorithm with DLC.

4 - Profit (for EA)

[Dvark 2]

I strongly suspect they actually have a decent simulation engine but they have stripped it down to reduce the min system requirements.

 

They assume most people wont notice if the simulation is garbage but they will if the game wont run on their laptop.

 

They are probably right.

 

It makes me sad.

[SirChick 184]

It is possible however.
 

Since I'm no programmer, software engineer, or developer so I'm going to speculate.  Is it not possible to write a code which says:

[croxis 150]

On the issues of sims not remembering where they work: thats because sims don't actually persist at all.

 

 

Each building has a basket of resources with a number, from money to food to people. So a house doesn't have "Billy Bob" and "Sue Sim" stored inside - just the number 2 in the people basket. When a house sends someone to work it creates an agent (car or a walker), subtracts 1 from the house people basket, adds one to the agent's people's basket. The agent moving system then moves the agent to the nearest building which is broadcasting "I need people", despawns the agent, and adds 1 to the office's population basket. 

 

Same with water, power, sewage, and firefighters.

 

The ultimate hope is that the end result would be the same traffic flows as if every sim was always persisted.

 

This isn't in and of itself a bad way to do things.

 

Oh correction: pathfinding uses a D* based system, not A*.

[thunder071 0]

very enlightening topic but since i don't own the game i'm confused about the agents.  The engine crates them based on what? On population? Like for every 100 people, it spawns an agent or how exactly?

[john2218 8]

What is surprising to me that they didn't do, is with their finding the closest place to go, i.e. from home to work or home to a shop etc is why they didn't have the places fill-up as an agent routed to them.  Say for example, you take your low tech-low density industrial that supplies the 20 or so low tech jobs.  When a Sim leaves in the morning for work, why does this sim not send out a "ping" of sorts along the road to find the closest open job and then figure out a route there.  And when he does that it fills up one job in the factory.  So when 20 workers leaving their homes to go to work have pinged that factory and filled up the spots, it will effectively become invisible to the next ping that hits it.  To then handle if more than one person leaves at the same time, and to kind of make it more realistic in that not everyone always has a job at the closest place to them, have it assign a ping order randomly to the commuting Sims   So that way someone in the middle of a block could potentially receive the job closest to the residential area.  Using this system in opinion would be a very good way of giving a sim an actual fixed destination when he leaves for work and not a dynamic destination that causes him and the 40 cars behind him to u-turn at the end of the street cause the last job got filled up.  And it really would not take very much memory at all, because you're going on a per building status and not per sim (Although I think my 16gigs of RAM could handle remembering where all of my 220k sims live and work if they would let me )

 

And all this is even before worrying about the actual path-finding to these locations (which is an entirely different beast).

 

This pinging system could also work for garbage agents (maybe as an entire side of a street instead of individual cans, as you may still get a similar effect to what we have now), police, fire, medical and mass transit agents could all use the same sort of "ping and reserve" system.  That would solve a lot of the traffic issues, which can usually be attributed to the herd mentality of all going to the nearest job no matter what.

 

In the end I would be cool with sims not having a memory of where they live or work, I just want a game that allows me to build a realistic town, not a town that has to game the system in order to even achieve basic functionality.

 

TLDR:adding a destination reserving function for sims searching for a destination would help a lot.

Agreed 100%, should not use too much more computer power and would make everything work much, much better even without improved pathfinding....  Jealous I didnt think of it myself.

[Aphid 5]

I've commented this on the YT video, but will also post this here for people to read.

 

The following information presumes at least a little background in Computer Science. I will be providing links to relevant articles as things come up as well.

 

Let us consider the GlassBox engine and, as an example, focus on one small part of it. First, we restrict our scope to the garbage truck network. Like several other of the networks such as shuttle buses, police, fire, and healthcare, this is a 'pickup' network. Several vehicles travel the road network to a set number of places on this network to pick up some available good there.

 

In the interest of optimizing the flow of this network, we thus need to find some collection of paths for a number of garbage vehicles. Let's call this number k. For now, we will assume k=1, or that we have -one- garbage truck for the entire city. In reality the situation with more than one vehicle is only going to serve to complicate things further and increase the computational load for arriving at an optimized situation. We are also going to assume that the city does not produce enough garbage to fill up the truck entirely. Again, the same logic applies, if the city was capable of doing this it would only complicate things further for the algorithms at work.

 

Now for the math bit:

 

The road network of your city can be thought of as a directed graph. On this directed graph G[V,E] we wish to find the shortest path that arrives at a certain subset S of nodes. This particular problem is widely known through computer science as the 'travelling salesman problem'. The problem is part of a set of problems also labelled 'NP'. This stands for 'Non-Polynomial-Time(-Problems)'. http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf see also pages 250-257 for the Travelling Salesman Problem in particular] There is no known algorithm for strictly solving this problem class other than to try every possibility. The amount of ways one can travel through a directed graph is the total amount of hamilton cycles in a graph. A hamilton cycle http://mathworld.wolfram.com/HamiltonianCycle.html is a sorted collection of points containing every point v in V of G at least once, and where every i'th point has a connection e in E to the i+1'th point. Through a bit of combinatorics it is possible to prove that (n-1)!/2 is the total number of Hamilton Cycles in a non-directed graph. For a directed graph it is (n-1)!.

 

(n-1)! is a very large number even for relatively small amounts of nodes n. Every property of the city is essentially a node for the garbage network. Thus finding out the best possible route for all possible cities with more than ~20 houses in a timely fashion is not possible because of physical limitations. (The amount of atoms and hence transistors in a regular chip combined with physical limits on clock speeds due to overheating) and requires quantum computer power at the very least. Additional proofs in computer science link different NP-complete problems together, where a solution in one can imply a solution in another. All NP-complete problems are at least of order {2^n}. Hence my comment about it at least needing this amount of operations to reliably arrive at the optimum solution.

 

Back to the problem now;

 

With this knowledge, we arrive at the conclusion that doing the best possible is impossible. So one settles for the next-best thing, an approximation. We can take a random educated guess at a hamiton-cycle that takes only O(n log n) time, an unnoticeably little amount of it, even with millions or more agents and nodes in our graph it takes less than a millisecond of processor time.  Then we can consider each pair of nodes in this cycle and rearrange them if it improves the end-result. The same for each triple, quad, etc, however high an order we can go. In other words there are O(n^2) approximation algorithms. In practice this yields decent results. Of course, n^2 will still get out of hand if we consider a large interconnected region a la SC4, and there are possible pedantic examples that will make many approximation algorithms like the one just sketched out behave (very) poorly. 

 

Since finding the shortest route (A*) is about an O(n^2 log n) algorithm http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html it makes sense to go for the (n^2) option.

 

All these issues and expensive computational requirements pretty much reveal the reason behind all the arbitrary limitations this game has put up. Or the fact that the scale of things is off by a country mile, about a factor 4, from real life. A 2-lane road does not take up 20m+ of space. Many cities have two-lane roads with housing blocks inbetween (two rows of housing) only 50 metres apart or less. SC2013 forces about 200 metres to do the same. Looking through readily available information, the UK for example has a road width of 5.6 metres for a two-lane city road that qualifies for a 30 mph speed limit. Even with sidewalks of 2m each that amounts to less than half the space it takes up in this game.

 

Even the size and scale of objects such as houses is quite off and cartoony. It is a trick that was previously employed in lots of other games so that they could run on old hardware. Looking at the game's graphics it's not so much the 'style' of the graphics that causes the unrealistic feel as the relative size of things. Simcity 4 is a reasonable enough approximation if I compare it to an aerial photo or sattelite view of the real world counterpart.

 

In fact, cities built to resemble real-world counterparts in SC4 by using mods and other customizations have an amazing resemblance to the real thing. SC2013 is right in the 'uncanny valley' where this is concerned.

 

Anyhow, the second trick employed is the fixed regions. By having the pre-planned regional transit system the pathfinding cost is greatly reduced. Pathfinding for this part of the system can be pre-computed and a vehicle travelling to another city only has to travel to the exit point of this city, then along a preprogrammed path on the highways, before coming into the other city at a pre-prepared entry point.

 

Unfortunately, even if we had computers 100x more powerful, improvement significant enough to bring this game to the same size and scale as SC4 has is not possible. This means actual to-scale glassbox simulation with proper pathfinding is unlikely for at least three more decades. Why did the developers not realize this? In my humble opinion, the whole glassbox thing is a waste of processor power for at least a major part of the systems it tries to simulate. It could be far better spent making SC4 a seamless experience; where the user will not see or know about the square 'city boundaries'. Income/expenses is simplified through being region-wide, and only a relatively small area around where the camera currently is pointing is simulated. Or actually making the spline-based road networks viable by having non-rectangle buildings. Flexible buildings that can distort their shape more than the current implementation, vertically (more or less floors with more/less occupancy), length/width, and curvature. Corner buildings for 90, 45, 135, 30, 60, etc. angles. The roads are flexible but the buildings are still fairly rigid. Hence there is not much of a point to the flexible roads.

 

Why is some of the glassbox a waste of processor power? Consider the system for power (the kind measured in Watts, not FLOPS/IOPS). Power packets are sent to induvidual buildings. Yet all this accomplishes is that the actual power in the city is approximately

 

min(R, P*(1-e^(-L*t))) 
 

Where R is the power Requirement, P is the power production. The approximation is actually very precise for cities with more than a few buildings, and depends on the granularity of the simulation. This is the exact solution of the differential equation involved, while the SC2013 simulation simply results in a certain famous approximation of the solution - Newton's Method. http://de2de.synechism.org/c3/sec36.pdf Any partially powered buildings are unpowered as far as the simulation's concerned. In fact, simply sorting the buildings on weighted euclidian or travel distance to the power plant(s) and then 'magically' powering each building; deducing the power requirement of this building from a total 'pool' of power until the next building does not have enough juice will result in the same behaviour especially when the pool's size is actually 

P*(1-e^(-L*t))

for a single power plant with power P. Multiple power plants then net you a linear combination. Calling the second part of the factor F1, F2, ... ,Fn we get P1*F1+P2*F2,...,Pn*Fn for n power plants producing P1,P2,...,Pn power. 

 

So basically all the extensive expensive pathfinding for each induvidual packet is a waste, for a single pathfinding call can serve well for each power plant. Then the same by extension applies to water, sewage, garbage* and all other systems that function in the same way.

 

*Garbage can work this way if we forego collection mechanisms and treat it as a 'reverse' power system. Garbage trucks would merely improve range and/or capacity and be superficial representations instead of doing the work. Sewage already works this way except for situations where the road can't handle the sewage volume. (which is a bit rediculous anyway.)

 

As for all the 'service' networks, while the Glass Box idea is a better approximation of reality, the sad truth of an NP-complete problem means you can't get a match, or even as close as reality gets to an actual solution of these problems. Why bother with it at all when a quantitative analysis method as employed in every previous game gets you close enough? Refining the quantitative methods used* prior will get you an experience near-indistinguishable from current, yet at orders of magnitude less system resources consumed. Thus allowing an actual to-scale simulation.

 

*E.g. coverage areas based on road networks and their congestion levels; traffic that is actual cars but which take a probabilistic approach as to which route to take at each intersection dependant on a pre-computed quantitative traffic map.

The actual cars spawn at sources in predetermined intervals and go onto the road. Whenever a car reaches an intersection or node with a sink there's a chance it will go to that sink equal to that sink's occupancy level // the total precomputed traffic level on the road. No expensive pathfinding is thus needed for normal cars to get a system that behaves quite similar to the current one. Of course you couldn't see where each induvidual sim is going, but you can't really see that now either.

 

What about the service vehicles? That is still an open question.

[MandelSoft 2,775]

^^ Thank you for this elaborate post why Glassbox doesn't work backed up with mathematics. Yet another reason why the old simulator was better; the NP problem makes the Glassbox very hard to handle, probably Maxis is over-ambitious with this one...

[snwboardn 18]

very enlightening topic but since i don't own the game i'm confused about the agents.  The engine crates them based on what? On population? Like for every 100 people, it spawns an agent or how exactly?

Technically people are not agents just visual representations of numbers... An agent is basically a ping packet, that says "I am a job I need 10 people" , it shoots out from a job or a shopping center and hits the first number it sees, a number being a house with 10 people or a building with 200. The problem seems to be that it doesn't seem to change the ping packet so that same ping packet keeps going around the board saying "I need 10 workers" When in fact there are already 100 workers on their way, they just haven't gotten there yet. It almost reminds me of how a broadcast storm starts when you plug in a bunch of hubs together. 

 

It is the only way you can do agents without having a 1:1 ratio of agents to sims. If each sim sent out their own "ping", it would eventually be too much to handle. 

 

I don't know if anyone has played Cities in Motion but they do a much better job at giving the illusion of a living breathing city... I think it has it's own pathing problems but it does a decent enough job that I have never noticed anything on this magnitude. 

[Bibor_Kiraly 21]

I truly hope "Advanced Pathfinding" is one of the features they turned off at launch (along with Cheetah). Otherwise I'll seriously put this game on hold and fire up SC4 with NAM again.

[blunder 1,080]

I've commented this on the YT video, but will also post this here for people to read.

 

I wish the rep service was running so we could +1 this thing to the moon.

 

As for all the 'service' networks, while the Glass Box idea is a better approximation of reality, the sad truth of an NP-complete problem means you can't get a match, or even as close as reality gets to an actual solution of these problems. Why bother with it at all when a quantitative analysis method as employed in every previous game gets you close enough? Refining the quantitative methods used* prior will get you an experience near-indistinguishable from current, yet at orders of magnitude less system resources consumed. Thus allowing an actual to-scale simulation.

 

Exactly.  What was Maxis thinking?  Engineers don't do a Finite Element Analysis on ever last nut and bolt when building a bridge because the established quantitative methods and experience get you what you want with FAR less hassle; what makes maxis think doing it the long hard way would work any better for them?  Oh well, they're learning the hard way now.

[mastorofpuppetz 199]

I knew there would be server issues on launch and I was willing to put up with that. But reading this thread, and seeing that even the underlying ENGINE and gameplay are a mess too - that's really sad  

This stuff sounds so fundamental and wide reaching, I'm not entirely confident it will get fixed.

 

 

They HAVE to fix it... otherwise Maxis will fold.  This will end them.  People won't even blame EA anymore.

That's a programmatic error, not a marketing, launch or DRM issue.

If they can't program a game, then what's the point of being a gaming company?

 

 

The argument could be made, forcing the game to run on servers severely limits the simulation as simming a game that uses an advanced simulation engine with thousands of gamers at once is really strenuous on a backend server/database.

 

BUT the decisions to sim every single sim doomed this game it was not needed, a waste of resources and time. It is A city building management game not a game called "The sims in the city" The engine is incapable of really simulating a city, it falls over itself. A small town it's manages.

 

 

Sadly, I think the entire design of the game is flawed and not repairable. They really made this a disaster. Who would have thought the launch issues were only scratching the surface..... I am sad what has happened I was really excited and a proper new simcity.

[Board_Marshal 104]

 

I knew there would be server issues on launch and I was willing to put up with that. But reading this thread, and seeing that even the underlying ENGINE and gameplay are a mess too - that's really sad  

This stuff sounds so fundamental and wide reaching, I'm not entirely confident it will get fixed.

 

 

They HAVE to fix it... otherwise Maxis will fold.  This will end them.  People won't even blame EA anymore.

That's a programmatic error, not a marketing, launch or DRM issue.

If they can't program a game, then what's the point of being a gaming company?

 

 

The argument could be made, forcing the game to run on servers severely limits the simulation as simming a game that uses an advanced simulation engine with thousands of gamers at once is really strenuous on a backend server/database.

 

BUT the decisions to sim every single sim doomed this game it was not needed, a waste of resources and time. It is A city building management game not a game called "The sims in the city" The engine is incapable of really simulating a city, it falls over itself. A small town it's manages.

 

 

Sadly, I think the entire design of the game is flawed and not repairable. They really made this a disaster. Who would have thought the launch issues were only scratching the surface..... I am sad what has happened I was really excited and a proper new simcity.

 

"The Sims in the City".  You know, that's pretty good.  I've pondered several legitimate alternative titles for this game and this is by far, in my opinion, the most accurate name for it.  It still focuses that it's "city" centric (-town, -ville, whatever...) but because of the Glassbox "agent" modeling, the "Sims" component of "The Sims in the City" is perfect.  It's Brilliant.  Kudos.

[theBrad 25]

I don' understand what all of you are bickering about.  This morning I woke up in my basement studio apartment, got in my car & rather than wasting my time on the freeway, I drove down several narrow dirt roads to get to McDonalds where I work.  After work, I found out there was a closer home to work, so I drove to a lovely 8 bedroom mansion.  I woke up the next day and as I now live in a mansion, I should certainly look the part & I now am a CEO of a Fortune 500 company.

 

Makes sense doesn't it?

[WIbigdog 3]

I don' understand what all of you are bickering about.  This morning I woke up in my basement studio apartment, got in my car & rather than wasting my time on the freeway, I drove down several narrow dirt roads to get to McDonalds where I work.  After work, I found out there was a closer home to work, so I drove to a lovely 8 bedroom mansion.  I woke up the next day and as I now live in a mansion, I should certainly look the part & I now am a CEO of a Fortune 500 company.

 

Makes sense doesn't it?

Yeah, then you go back to work at McDonalds the next morning in your Maserati to flip burgers in a suit.  Best burger flipper ever.

[Titanicbuff 1,262]

heck of a traffic jam

[aaronlbarta 6]

Smoke and Mirrors??

 

Anyone else feel this about the glassbox engine, When i saw the early videos of how the simulation was going to be ACTUAL reprentation of whats going on and not a simulation, I thought to myself...... wait..... wasn't SimCity 4 pretty close to representing a true life city.   I felt the simulation in there is alot more accurate.... in SC4.

 

It's annoying how the game takes forever to realize i bulldozed my old power plant and built my new one. I try the SC4 technique of pausing the game to help not disrupt my city.... seems like old habits die very hard. This game is good, but Maxis needs alot of tweaking. I feel like its pseudo-simcity.

[Tarkus 6,933]

Oh correction: pathfinding uses a D* based system, not A*.

 

For those who aren't familiar with the differences between A* and D*, D* is, in general terms, a "dynamic" version of A*, where changes in costs can occur in the same cycle.

 

I suspect what's at play here is something similar to what happened with SC4's traffic simulator (which was A*-based).  They've tuned the heuristic value to a low level to minimize system strain, and the value is so low that it's basically turned the simulator into a shortest-distance simulator.  SC4's traffic simulator, with the heuristic value tuned properly, is actually pretty good--but it took community modification (with Maxis encouragement--there were discussions between MaxisFrank and the7trumpets and toroca way back in 2003 about this on the old EA official forums).

 

-Tarkus

[K-os 30]

I don' understand what all of you are bickering about.  This morning I woke up in my basement studio apartment, got in my car & rather than wasting my time on the freeway, I drove down several narrow dirt roads to get to McDonalds where I work.  After work, I found out there was a closer home to work, so I drove to a lovely 8 bedroom mansion.  I woke up the next day and as I now live in a mansion, I should certainly look the part & I now am a CEO of a Fortune 500 company.

 

Makes sense doesn't it?

Yeah, then you go back to work at McDonalds the next morning in your Maserati to flip burgers in a suit.  Best burger flipper ever.

 

Unless someone beat you to your job at McD's and you're off to line up and find the next one. LOL!

You have to admit though, it'd be an interesting life.

[el.lopan 54]

I don' understand what all of you are bickering about.  This morning I woke up in my basement studio apartment, got in my car & rather than wasting my time on the freeway, I drove down several narrow dirt roads to get to McDonalds where I work.  After work, I found out there was a closer home to work, so I drove to a lovely 8 bedroom mansion.  I woke up the next day and as I now live in a mansion, I should certainly look the part & I now am a CEO of a Fortune 500 company.

 

Makes sense doesn't it?

Yeah, then you go back to work at McDonalds the next morning in your Maserati to flip burgers in a suit.  Best burger flipper ever.

 

 

 

 

That's Communist SimCity, comrades, private property is no more. Everything is everyone's!

[T Wrecks 10,210]

In Soviet SimCity, job gets you!

__________________

 

But seriously - Aphid, thank you very much for this long and elaborate post. +1 from me!

 

Especially for the power system, the engine used in SC2013 always looked like overkill to me. I never understood why you would want to make any more calculations than these:

- if consumer close enough to a power line, then connected, else unconnected (=> blackout)

- if the total power demand of all connected consumers is less than or equal to the total available power, then everybody happy, else blackouts

- marry the princess and live happily ever after

 

If you were trying to add advanced features, you could implement power demand fluctuations based on time of day, and power supply for base load / short-time peak load. The result wouldn't feel to wacky and unrealistic, I guess, and the algorithms behind shouldn't be a problem for any person who's trained accordingly

 

 

For the water grid, the height of water towers relative to buildings (and the consequences on water pressure in the lines) as well as ground water level are interesting factors that make the simulation somehwat more complicated, but still I don't see anything that speaks in favour of agent-based simulation.