This is cool, but it's a completely different goal. This is exactly the part that is not simulated in a game like CS or the Simcities. Designing and building a city is what constitutes your game, so you would not want to let the software do this part.
At least they use the fastest route, not the shortest. However, that's probably the same, as faster routes have longer segments, so the algorithm probably just counts lane segments. The whole route is calculated before the trip starts and usually only gets recalculated if there's a fire somewhere. I think the number how often the mode of transport is allowed to change is limited to three or so. They won't calculate this for more than 16k vehicles, and there are maximally 65k citizen instances, not all of which travel at the same time. Those vehicles and traveling citizens are always on the map.
Well, I said the game uses segments. Anyway, as I don't know Unity, I was talking in general. All the Simcity games for example use literally "shortest". They just measure distance. Which is the reason why the traffic simulation is so shitty in them without mods.
All transport lanes are split into segments (maximally 32k). A faster road has longer segments. The game chooses the route with the fewest segments.
It may exist, but it is not used properly in most existing simulation games, because the CPU overhead is too high, given the number of active agents. Simcity 4 from 2003 got a proper calculation of a the fastest route with the NAM mod a few years after release. The SimCity game from 2013 never got one, it still uses just shortest distance without adjustment.
The SimCity games don't weight. They measure exact distance. If a tiny gravel road is one centimeter shorter than the motorway to the same destination, any SimCity game will choose the gravel road and not use the motorway.
I can only state that you seem not to know any of the common city simulation games, otherwise you wouldn't react this way.WOW.. Are you just pulling this out of your ass as you go...?
Well, so why don't SimCity games manage to calculate the fastest route then? Which is a fact.
Which is what I said and which shows who is the mouth breather here.
You just fail at thinking, otherwise you would have grasped the concept of segments (the distance between vertices, also called that in the code). And regarding the calculation overhead, SimCity 4 didn't run well even on better computers on release. It's still somewhat taxing for computers today, 12 years later. They indeed cut the weighting because of performance reasons. A proper calculation of the fastest destination was added about 3 years later with a mod.
struct waypoint
{
waypoint *parent;
vec o;
vector<ushort> links;
int score;
waypoint() : parent(NULL), o(vec(0, 0, 0)), score(-1) {}
waypoint(const vec &o) : parent(NULL), o(o), score(-1) {}
};
void findroute(int from, int to, vector<ushort> &route)
{
if(!waypoints.length() || !waypoints.inrange(from) || !waypoints.inrange(to) || from == to)
return;
//determine scores
loopv(waypoints)
{
waypoints[i].score = waypoints[i].o.dist(waypoints[to].o);
waypoints[i].parent = NULL;
}
//recurse
waypoint *cur = &waypoints[from],
*first = cur;
while(true)
{
int lowest = -1;
//try the "series of low scores" method
loopv(cur->links)
{
waypoint &l = waypoints[cur->links[i]];
if(cur->links[i] == to ||
( !l.parent && &l != first &&
(lowest < 0 || l.score < waypoints[lowest].score) &&
(l.links.length() > 1 || (l.links.length() && !waypoints[l.links[0]].parent))
)
)
{
lowest = cur->links[i];
}
}
if(lowest == -1 && cur == first)
return;
else if (lowest == -1)
{
cur = cur->parent;
}
else
{
waypoints[lowest].parent = cur;
cur = &waypoints[lowest];
}
if(lowest == to)
break;
}
//cur should still be the destination
int i = route.length();
while(true)
{
route.add(cur - waypoints.getbuf());
if(cur == first)
break;
cur = cur->parent;
}
//now we optimise the route, we start at the back and check the latter nodes for common nodes
//common nodes include unused nodes between two nodes in the route (a shortcut)
// as well as nodes which have a link to one of the nodes later in the vector
///just remember the vector is in reverse
///we also start at the end of the prior movement vector; we don't want to miss out critical destinations.
for( ; i < route.length(); i++)
{
//don't bother checking i + 1
for(int j = route.length() - 1; j > i + 1; j--)
{
waypoint &chk = waypoints[route[j]];
//see if there are shortcuts available; take them!
if(chk.links.find(route[i]) >= 0)
{
route.remove(i + 1, j - i - 1);
break;
}
//see if a shortcut can be taken by using 1 intermediary node
//we don't check for more
if(i + 2 <= j)
{
int found = -1;
loopvk(chk.links)
{
if(waypoints[chk.links[k]].links.find(route[i]) >= 0)
{
found = k;
break;
}
}
if(found >= 0)
{
route[i + 1] = chk.links[found];
route.remove(i + 2, j - i - 2);
break;
}
}
}
}
}
Those are two different algorithms. I've implemented both.
