Itsy bitsy coder

So back into the strat portion of the system, but the real “strat” part of it. It always feels a little weird.

The gameplay portion of strat was largely Marty’s work, I believe, and outside the interfaces with certain other people’s cyclic linked lists and such, Marty’s code was always pretty readable. I don’t mean readable the way a half-decent open source project will be, I mean the kind of code you find yourself pointing at and saying “ooh”.

What makes it weird is that when I go in there now, so much of the old code is gone and replaced with my systems. But when you’ve spent 3 years walking thru a minefield, you learn to tread lightly and expect disembowelment.

So, for instance, I find myself needing to add a rule that says “You can’t move a brigade across a hostile link”. Ok, that’s real easy. That will be in StratHCUnits::deployPermission, when manualMove == true. When I check for a link, just catch the link, call link->checkDepots() and check that link->hasEnemyFirebase() is false.

Now – how do I say that?

The few minutes it takes you to realize that its actually that easy is like skipping lunch to go check your bank balance and finding more zeroes on the end than you thought. Well, ok, the more zeroes the weaker the simile :)

BRIGADE_MOVE_RESULT
StratHCUnit::deployPermission(const CPStruct* cp, bool manualMove) const
{
  ...
   // We must already be at the CP or directly
   // linked to it. If a link is involved, return it
   // to us so we don't have to look it up again.
   if ( hasLinkTo(cp, &link) == false )
      return BMR_FAILED_LINK ;

   // If the brigade is being moved and a link is
   // involved, it must be entirely controlled by us.
   if ( manualMove == true && link != NULL )
   {
      if ( link->endDepot->side != side()
           || link->startDepot->side != side() )
         return BMR_FAILED_ENEMY_DEPOT ;
      if ( link->hasEnemyFirebase(side()) == true )
         return BMR_FAILED_ENEMY_FB ;
   }
  ...
}

I added the new fail codes to the Brigade Move Results table (js version) and a conversion to text (won’t be localized until the next client release), and ticket #1326 completed.Slightly scarier was a change to the firebase system. This has been a traditional terror zone for everyone at CRS. For those of you who have managed dev teams, the original system experienced a multiplicity of failures to communicate – #1 both programmers involved failed to understand the intent and desire of the FB system because of #2 their previous misunderstanding of the strat system as a whole and #3 failed to communicate the problems occuring during implementation. When problems arose and were tasked to one of them, #4 usually the wrong one, they would #5 simply botch it to make it not do that.

A few years ago, I threw away some 9000 lines of FB code and wrote the FB system from scratch in 973 lines. Part of the old complexity came from trying to coerce the link between towns as a single entity when the underlying system has one “link” for each direction.

My first question was “are the rules symmetrical” – and infact, yes they are. You can draw a little grid of owner/controller vs owner/controller for the two CPs at either end of a link, fill in the squares, and what you get is a simple ruleset that can be boiled down to five lines of code (though it formats out slightly longer here)

static inline bool
_fbsBetweenCPs(const CPStruct& left, const CPStruct& right)
{
   // If both towns have lost control,
   // spawning is impossible, FB uneccessary.
   if ( left.side != left.controllingSide
        && right.side != right.controllingSide )
      return false ;

   // Combined with the previous rule, this checks
   // for a link between two friendly towns.
   if ( left.side == right.side
        && left.controllingSide == right.controllingSide )
      return false ;

   return true ;
}

(You can draw your own grid from that if you feel like validating it). That there replaces 2015 lines of code, although a lot of that is duplication. If you eliminate that, it replaces 1331 lines of unique code :)

Having found a set of symmetrical heuristics, its a short path to replacing all of the other complexity with a code that looks at each link independently and housing it in what boils down to: determine what the new state would be, if it changes the number of open firebases, then act on it, otherwise leave things alone.

A simple, testable and stable state engine for the firebases means that the firebases are always in the “ready” state. When you blow a firebase, it just closes it and opens the firebase on the reciprocal link. Prior to 1.15, blowing a firebase could actually destroy several other FBs, code elsewhere in the FB system would detect this and put them back. It was only the fact that the updates to the other hosts went out within nanoseconds of each other (literally) that kept you from seeing it most of the time (but you probably remember occasionally seeing an FB blink? :)

So now we’ve introduced a slight complication of our own (+68 lines of code) which will open up the FB TownA -> TownB

TownA := Friendly town with 1+ army brigades
TownB := Front line (1+ enemy links) friendly town with no HC Units at all

If you move the brigades out of TownA the FB closes. If you move a brigade from TownA to TownB the FB closes and the link is re-evaluated (so the FB might potentially reverse).

We might open the rule up and replace the “No HC Units” clause with “no army brigades/divisions” but its not planned at this point.

Next up: I’m adding a restriction on the number of AOs that can be used for softcaps; this is really a temporary measure while we finalize a longer term plan. The trouble is we think boots-on-ground should be a part of all town captures, we considered options like “make the OIC/HC that posts the AO the one that has to cap it” and “give Killer a list of HC home addresses and ammo for his 12 bore”.

Kidding aside, “move a bde into a town gets you the town” we don’t like because (a) you can’t block it, (b) you can’t defend against it, (c) it allows you to take a town in under 21 minutes.

When softcapping isn’t prevalent, when there is actual to be had on the frontline, people do make the effort to defend their towns by driving an MSP there or dropping in paras. I’ve been to dozens of fun “soft” caps. We’ve won a few, lost more. So at best, we would want some kind of “Move Objective” which locks a brigade into moving into a “softcap” town.

This would be drawn from its own pool rather than the AO pool, and would automatically convert the town after – say – 90 minutes. If you want the town faster, boots-on-ground will work like a regular AO but take, say, 31 minutes instead of 21. That gives the defender a chance to interdict, but he has to move a brigade in if he actually wants to prevent the conversion, at which point it converts to a normal AO and counts against the AO pool.

A lot of work there including client and UI work which means it needs a lot more planning and design.

The short term solution isn’t wonderful but we’d like it ready for the next campaign: to place a softcap, you must first place at least one battle objective.

Speaking of the code itself… Amongst some of the proprietary code I don’t think I’m allowed to detail, there’s some genuine diamonds.I seem to recall Thunder raising his estimate of Marty’s design somewhat when I helped him get his head around one of the key workings. In hindsight, its not well named, but the name most people would give it today (sorry, I have to be cryptic on this) isn’t a great name either, IMHO. It’s like “spam” was a funny name when you kept getting them every few weeks, but if you were going to name it today, wouldn’t you call it “junk mail”?I recently described the same system to a friend at Gearbox who works on their AI and networking systems, and his eyes genuinely lit up :)

Oh – and since I’ve been typing away at this throughout the day, I’ve actually finished all of the above tasks :)

34 Comments

Meh, well “spam” was the original “same post across multiple” groups in newsnewt – not to be confused with velveeta (or however it was spelt).

todays random post was brought to you by the letters M, M, D and F

-asn

Which was so much fun to Y2K certify – did Demon convert completely to exim or are there any MMDF boobytraps left? Cause it was good for Y2K but only until 2038.

*head asplodes*

OT–neato code boxes with scroll bars and everything. Man, teknowlegdey rawks!

Sorry mike – that has to be a backronym, probably created for some American who didn’t know who Monty Python was.

It was only the fact that the updates to the other hosts went out within nanoseconds of each other (literally) that kept you from seeing it most of the time (but you probably remember occasionally seeing an FB blink? :)

Sonofa…. I bet this is why we used to think that FB’s would repair themselves, back in year one or two. They weren’t; they were being nuked and put back but put back in the repaired state by mistake.

Not by mistake – by dispurpose

Heh. I thought that was some form of X I hadn’t heard of. Methyl Methyl-Di-Fsomething.

Spam is not velveeta. Spam is Spam. A useless meat substitute that has the consistency of jelly and the taste of raw sewage. With salt.

So, if the producers could be convinced to so desire, would it be technically practical to add more CPs etc. into the midst of the mesh?

Unfortunately, the original designers thought the fighting was about control of towns per se…when actually it was about control of bridges and bridgeable river stretches, and to a lesser extent crossroads.

Players want a freshened game, CRS wants to retain the historical context…such changes to the mesh would do the job.

Not without TE2 – just takes too many man hours or more coders to code better terrain tools.

Hey, speaking about the strat host, in this thread: http://forums.battlegroundeurope.com/showpost.php?p=3007825&postcount=109 DOC said that you had said that it was too expensive to calculate the link distance between cities, or that a brigade has ot move, or whatever, for the purpose of throttling supply or calculating moving time across the map. Can you shed some light on what it is that makes it expensive? It seems to me that it should just be a simple graph traversal that with the number of CPs and links in the map shouldn’t take more than (my guess) less than a second.

On a slight side note.

What restrictions will naval & air brigades have when movin into a town given that they usualy move from a town with no direct link to their destination?

Or will their movement be governed by what the current ground brigade situation is.
ie, if the depot that prevents you moving another ground unit into the town is held by the enemy then you can’t move a air or naval unit in either?

It seems reasonable to me to require that a naval brigade only be able to move from A to B if there is an uninterrupted friendly waterway between A and B. Similarly, an air brigade can only move between A and B if there is a land route (because the support elements have to move by land). None if this silly warping of a naval brigade into some isolated city that’s been softcapped.

It seems to me that it should just be a simple graph traversal that with the number of CPs and links in the map shouldn’t take more than (my guess) less than a second.

And you believe that’s not expensive? Every time a facility’s state changes hands or a vehicle needs to be supplied or resupplied, or a brigade needs to move or an AO needs placing … locking the strat host for a whole second or two?

The strat spec calls for it to be designed so that routing calculations are integral, so that’s what CRS believe they have. It would be hard to imagine an implementation that made it more difficult.

What restrictions will naval & air brigades have when movin into a town given that they usualy move from a town with no direct link to their destination?

Until the Russians “camped” the airfields, 6th Army continually moved in supplies and equipment and troops by air. The idea of specific links between airfields is a bit … civillian.

As for naval brigades, almost all of the harbors do share a sort of implied link. Tying it to established naval links sounds sensible … except naval links exist between deep-water harbors. So kiss your fairmiles good bye.

Considering that CPs aren’t really known to move around (barring eventual implementation of continental drift and earthquakes ;) I would think that a data set could be trivially pre-calculated.

You’d only need distances between connected CP’s, right?

If it were all to all, then yes; I could see it becoming an unmanageable lookup table at that structure with it being numCP^2 connections, but at numCP*8 (or whatever the most-connected CP is), that’s not huge. It’d be a millisecond lookup, if not micro, yes?

If that’s the case then it becomes a question of “is this worth the time and added complexity?”

Umm, yeah I do… ;-) I mean, it only needs to be recalculated when a link is broken or established, which isn’t that often. Between those times, the cost is fixed so can be cached. Like you precompute the cost between every node and every other node and then just use that info.

I guess what I’m confused about is whether it’s the actual performance of e.g. the Floyd-Warshall algorithm that is too expensive, or if there’s something particular about the way the data is stored or used in the host that makes it expensive.

522 routable CPs.
1834 routing links.
6583 flow-control nodes (4227 route-affecting facilities).

[Krenn] Is that going to be a “next hop” lookup table with cascade failure retraining or is it going to be 522×521 grid of whole routes where you will update every member that is affected – e.g. when someone caps the St.Truiden-Tienen depot? [/Krenn]

And it has to be a fast lookup solution because the single threaded strat host processes 17000 queries per second during low-pop, so anything that takes more than a couple of miliseconds per second is out of the question.

You’re welcome to attempt to model a solution yourself, all the neccessary data is in Wiretap.

The factory-supply system is viable because its only consideration is CP ownership and it performs a trivial flood-fill. It takes between 850us and 25720us depending on how significant a change it encounters, however it also only runs every 5 seconds and then only if it detected a state change it is sure means a big update – which doesn’t take long at all to test (>1us). Replicating a similar test for an A* network or using something derived from FW can take upto 1ms for somewhere like Antwerp – and for just testing if the network grid is valid that is too long.

I must be misunderstanding the problem that’s being solved… I thought this was to figure out how long it would take a brigade to move from it’s current location to a new location, which is always one hop away. Thus, no pathing concerns that need to be updated…

*rereads thread*

Ah, I see where I went off the rails. The floated idea is to have things get slower the farther they are from the ultimate source of supplies, not just to be able to tell that Spontin to Dinant is X km, so a brigade moving at 19km/h will take x/19 hours to complete the move.

I was just looking at the Wiretap specs to find where the CP and link data was… Since I have a couple big and important proposal deadlines coming up, this sounds exactly like what I shouldn’t be doing right now… ;-)

Hokay, so… I got the link and CP data from Wiretap, built a graph with boost::graph and ran dijkstra_shortest_paths on it. Result: on average it takes my machine ~200us to calculate the distance from one particular cp to all cps, in the full link network.

If you cache these results and only do the calculation from cps that matter, which are those that have supply flowing to them, ie have brigades, then that’s what, like at most 100 cps, a total of 20ms. And that would only have to be redone when the link network is changed, which can’t be more often than every few minutes.

If you have a megabyte to spare, the lookup of the cached distances can be done with a greedy 522^2 matrix which should be extremely fast.

I guess the big question is if the 20ms delay that will happen when the network is updated and the cache invalidated (assuming queries to all cps come in all the time) is unacceptable? In any case it doesn’t seem *totally* unfeasable.

Well that was fun! Now it’s unfortunately back to my NSF crap…

Did you include ownership? When I ran my own optimized dijkstra on the CP network it took 185us until I added ownerships and then it took around 250us.

Did you include facilities? That starts to ramp up the time.

Did you swap the graph out of memory for each?

And yes, 20ms is absolutely unacceptable. Anything that takes longer than 1ms is unacceptable.

We’re not talking about CP distance here – we’re talking about routing distance. That means

1st Bde -> St.Truiden (CP: Own+Ctrl) -> St.Truiden Armybase (Fac: Side, Open) -> St.Truiden-Tienen Depot (Fac: Side, Open) -> St.Truiden-Tienen Firebase (FB: Side, Open) -> Tienen-St.Truiden Firebase (EFB: Side/Closed) -> Tienen-St.Truiden Depot (Fac: Side, Open) -> Tienen Armybase (Fac: Side, Open) -> Tienen CP (CP: Own+Ctrl) -> Tienen-Leuven Depot (Fac: Side, Open) -> Tienen-Leuven Firbase … Aarschot … Lier … Antwerp

By ownership you mean that not all links are open? I did not, I just worked on the full network graph. I guess I could download the current link state. Seems lowering the number of edges should make it faster, not slower, though?

I did not swap the graph out. It’s a megabyte, I doubt it would be swapped out. Out of cache maybe.

I did not include all the depots and firebases, it seems that’s a different issue. I mean, in your example, the states of st truiden CP, AB, depot, FB, other FB, Tienet Depot, AB, CP only does one thing, they decide whether the link between the two towns is open or not. The fact that there are several facilities that can break the link doesn’t affect the routing because from a graph perspective there’s no difference between

A—-B and A–C–D–E–B

wrt A-B routing if C,D,E have no other links. They can be merged into criteria for linking A and B. It does make the test for whether the link is open or not more complicated (you have to check all 8 facilities) but that must be preferable to making the graph have 8 times as many vertices and edges, most of which are trivial.

Or am I not understanding the routing process correctly?

You’re not understanding the routing process correctly.

You’re also not understanding the context in which it is going to operate. Like I said, the host process handles 17,000 queries per second off-peak from vehicle reservations, supply actions, movements, table bumps, spawn list requests, cp and facility status requests, building state updates/changes, spawn requests, despawn requests, etc, etc. All of which have to have very, very low latency. The graph is *not* going to be in cache about 90% of the time which is going to significantly increase the clock-cycle expense of working with it.

The depots/fbs/ABs/ownerships are *part* of the issue. Yes, of course if I had a well managed routing table it’s not expensive to look up. But the most efficient methods have a mangement overhead that is unacceptably expensive because of the number of flow-control nodes.

I thought it wouldn’t be “so bad” because its a map of two halves, but that’s a failure to understand that the map changes, and it has to be as efficient the day before map reset as it is the day the map opens.

It has to be as efficient when there is a major salient or two forming a pocket as it is when the front is a nice straight line.

Like I already said – the complexity isn’t the simple cp-to-cp routing map. If you have a cached map, do you recreate it every time a facility changes? If you do, what happens when 8 facilities fall within 2 seconds? Where do you get the CPU time to handle the other 34-90,000 other requests you had to process in that time?

Threading the graph isn’t an option – it means rewriting nearly the entire strat system, which affects all of the host processes.

The most obvious solution is to create a routing process, but the work involved in integrating that into an existing system is a major, major piece of work.

> You’re not understanding the routing process correctly.

Ok, thank you for clearing that up. ;-)

I wasn’t even bringing up the threading issue because I knew what the answer would be… I had in mind more of a “lazy caching” system where whenever a route was asked for that wasn’t calculated, the calculation would be done and cached. When a CP changed hands, the cache would be invalidated, but no immediate recalculation would happen. If the route requests are sparse then that scheme *could* perhaps decrease the latency to acceptable levels, but if you within the first ms get queried for all routes then you’re still in the shitter from a latency point of view.

Anyway, I think I have satisfied my curiosity as far as understanding what kind of prohibitively expensiveness was the issue. It seems the killer is the latency requirement in combination with the single-threaded process, not so much the actual expense of operating on the graph. Which is good, I guess — it at least means it can be engineered around easier than if it was the raw computational requirement that was the issue?

I’m happy I don’t have to deal with these kinds of performance requirements in *my* daily coding. The only issues are raw floating-point performance and how many cpu hours you can invest in it… Seems much less stressful. ;-)

Just had a thought: if this system is only to be used for supply routing, and supply flows exclusively from the 9 factory towns to all other CPs, wouldn’t you actually only have to call dijkstra 9 times? And cache the distance from the 3 factory towns to all CPs instead of the n^2 thing. (With the link states from the current game, it takes 1ms, still in-cache performance, to route from these 9 to all CPs.)

kfs1 wrote:
The factory-supply system is viable because its only consideration is CP ownership and it performs a trivial flood-fill. It takes between 850us and 25720us depending on how significant a change it encounters

It’s a simple floodfill system, vastly more efficient than djikstra. If you introduce distance measurement the frequency of refresh and the cpu-cycle expensse goes up massively and unacceptably.

The most obvious solution is to create a routing process, but the work involved in integrating that into an existing system is a major, major piece of work

I think i know of the perfect product to fix this – scales pretty well, written in a easily customisable language and you’re already familiar with it… unfortunate choice of acronyms however ;)

come on, dig out that copy of burpd!

-asn

You know, I think I made a deliberate effort to keep burpd at arms length. Didn’t Peter write that? The name sounds like a Ronald special (I can see him now, sitting with his plimsols on a conference room table, eating rice out of a PuE container and looking up saying “How about Bloody Useless Routing Protocol. Hahahahaha. Eh?”

Killer always had this notion that the coders would just plug in some kind of network routing algorithm. There are aspects of the design that bow to that notion – each object is represented with a “dotted quad” (although there are 6 of them not 4 – x, y, id, type, class, subtype, although we only actually use x, y and id since they are sufficiently unique).

You also have to remember that this graph doesn’t change or get queried randomly. Typically you want to move a brigade when its in an area in combat or trying to reach one. The host will most frequently want to query delivery routes for a brigade that has been/is in combat and therefore most likely to see routing changes. The most non-trivial queries are going to occur where they are most expensive and least desirable on a regular basis.

I was thinking something along these lines

ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-754-2002.pdf

Imagine there’s …
routes being congested due to the amount of supply flowing along them
HCs having to prioritize supply
brigade stacking becoming ineffective because it causes supply lines to that town to saturate.
Large towns becoming valuable because they control the supply arteries

You may say I’m a dreamer
But I’m not the only one
I hope someday you’ll join us…
;-)

Geeks make the world go ’round.

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: