Packet routing

[Karsten75]

Virgil, I tried searching for the A* algorithm that one of the game pods mention what you use for routing, but I have had no luck. Maybe I forgot the correct name of the algorithm?

Anyway, I was messing around and saw what I thought was packets that did not follow the shortest route to their destination.

Here is a short YouTube vid:

If you look carefully at the packets traveling to the blaster on the bottom left, you will see that they take more nodes going via the collectors than they could have taken going via the relays. Some of the packets on the second line exhibits similar behavior.

Am I missing something?  I thought I saw something similar in a game I was playing, but in the game I did not have the luxury to stop and try to figure things out.

I can recreate this better if you need to, or I can send you the base map, if you prefer.

[knucracker]

A* explained:
http://en.wikipedia.org/wiki/A*_search_algorithm

You may also want to read about dijkstra's algorithm:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Note that packets do not follow the path with the fewest nodes, they follow the overall shortest path (distance measured).  The two paths in your video to the lower left blaster are very close to the same length I would guess.  But the lower path might be every so slightly shorter (the first relay is higher up than the first collector is low).

[Karsten75]

Hmmm... Thanks for the links.  Dijkstra is like a god.

I thought it would count hops only, not also distance. In electrical terms, all distance is meaningless, it is only the delay in encountering a router/hop.

[Aurzel]

this isnt electricity though remember ;)

[Karsten75]

So these are not energy packets?

[Aurzel]

i fail to see how energy packets are even remotely like electricity apart from that they're both used to power stuff (though in very different ways)
and btw if you want to play the electricity card, lets remember that longer distances mean that the electricity has to travel through more electrical wires, which cause some resistance, therefore shortest distance is still preferable

[Karsten75]

i fail to see how energy packets are even remotely like electricity apart from that they're both used to power stuff (though in very different ways)
and btw if you want to play the electricity card, lets remember that longer distances mean that the electricity has to travel through more electrical wires, which cause some resistance, therefore shortest distance is still preferable

Doesn't the speed of electrons through a medium such as copper depend more on the thickness (diameter) of the medium than the distance? And what if these are fiber-optic links? Why would you fight a future war with stuff that offers more impedance than at least, say, fiber-optic?

[Aurzel]

even assuming optimal transport there will always be some resistance, therefore you need to have as small a distance for it to travel as possible

[Karsten75]

even assuming optimal transport there will always be some resistance, therefore you need to have as small a distance for it to travel as possible

Now we get back to routing algorithms. There are some similarities here to GPS routing. When you use a GPS, you can choose "Shortest Distance" or "Shortest time." The time-based algorithm might route you a little way longer, but use more highways (less traffic lights and stop signs).

So if you want to start calculating distance-based delays, you cannot exclude routing delays that might occur drom additional nodes on the shortest path. if you route with relays, there are about 2 collectors for the reach of every relay.

If I remember right, Virgil somewhere said that there was a small delay at every node (I think this may be because the packet has to calculate the route if I understand the A* algorithm correctly) and hence a packet traveling over more relays might travel faster even if it does have to travel a little further.

[Aurzel]

no the package calculates its route before it leaves odin city i believe, and if you consider GPS, there are too many variables on roads to be comparable traffic/lights/speed bumps/speed limits/road condition/number of lanes/etc

[deathly_god5]

There's a delay at each node, if you watch carefully the package stops at the node for a couple milisecs or something, just long enough to be noticeable if your paying attention but not if your not looking.

[knucracker]

The only delay imposed by a node in a path is that the packet can't skip over a node.  At slow speeds, this is zero or negligible.  As you build speed structures the packets speed up.  But, no matter how fast they travel (speed is distance moved per game update) they will always stop at each node.  In this case, the nodes impose an effective transmission delay.

The path routing algorithm does not assign a weight to the nodes.  I could have done that, but to be accurate it would have needed to factor in the effect of the speed structures.  The delay imposed at a node is also not necessarily constant as the 'delay' imposed on a given packet depends on how fast the packet goes and the distance between two nodes in the graph.  Each game update the packet hops so far down a link.  Sometimes, the distance between two nodes will be exactly 5 hops (for instance).  Sometimes it might be 5.01 (which would require 6 game updates to get the packet between nodes).

Factoring all of this into the routing algorithm might have produced a more accurate result in some situations, but it isn't always the most visually intuitive.  It also would only matter at higher packet speeds.  These things together made me decide to set the node delay to zero in the routing algorithm.   

[deathly_god5]

Oh didn't know that. It's just that before you build any of the speed upgrades it looks like the package slows down or stops, if only briefly (couple milisecs if that) , whenever it hits a collecter or relay.

[Aurzel]

even if it did stop for a couple of miliseconds, you're in no position to say deathly, the human eye cant detect anything shorter than into the tenths of a second lol

[deathly_god5]

True I forgot about that. So then why does it always look like (before speed upgrade) that is stops or slows down whenever it hits a collecter or relay?