Map Dimensions

[Mac_MatrixForum]

Hi Dave,

It would be very interesting to hear what kind of optimizations you have done for your route calculations. I do programming for a living so that's why I ask [8D]

[DanOppenheim]

Yeah, as another programmer I'd be interested in any technical details. Does the path planning follow anything like the same hierarchical system as the order planning? Does the command unit path to its destination then its subordinates use that as a base or does every unit do its own path? I can see pros and cons for both approaches.

[Panther Paul]

ORIGINAL: Franklin Nimitz

That's 400 units on-map right? No matter the size of the Force List OOB so long as it's not all on the map? e.g. if say some intrepid soul compiled the OOB for 12th Army Group, but most were no show status, or exit/enter at seperate non-overlapping periods, then that's fine?

Hi,

Yes thats right, its only the units on map that put a load on the system.

In fact on a map with terrible terrain you could proably get away with more as the route finding would be channeld down the road network, i.e. less searching across the whole map for a route.

[Arjuna]

Mac and Dan O,

This is a very complex issue and one that would probably bore the pants off most of our customers. What's more I really need a white board to explain it. The short answer though is we use as the basis the A* route calc method. Do a search on A* or AStar and you should find info on it. It's sometimes referred to as the marching ants algorythm as in its purest form it expands out from the start loc in all directions. If we just did that route calcs would take forever on large maps. So we apply a mountain of heuristics. We also have different heuristics for different route types - avoidance, asclusion, direct, shortest, covered etc.

When subordinate receives orders he bases his route on the boss's route if he is moving in formation with him. But he offsets this by the formation offset. However, to handle issues like not crossing over rivers etc, we apply a swag of heuristics to this as well. And then there's the issues of mixed mode movement, where we need to creqate effective start and end locs and RVs. Furhter we sometimes split the route for bridge building. We could talk for hours on this but hours I do not have right now. I hope this helps though.

[Fallschirmjager]

ORIGINAL: Prince of Eckmühl

ORIGINAL: Arjuna

Yes they are just a soft limit. Do I take it you would like to push the boundaries some more?

Hi Dave,

So long as there are Windows boxes that can handle the load, I believe that it would be worthwhile to take the engine to it's limits. One of the criticisms of y'all's games has been that they lack a larger "campaign level" of play. However, so long as "operations" are limited, geographically and chronologically, this doesn't have to be a deal-breaker. I've been looking at Salerno, circa 1943, and can't help but wonder if that wouldn't make a dandy "short campaign" of ten days, or so:

Please make this [&o]

[FredSanford3]

ORIGINAL: Panther Paul

ORIGINAL: Franklin Nimitz

That's 400 units on-map right? No matter the size of the Force List OOB so long as it's not all on the map? e.g. if say some intrepid soul compiled the OOB for 12th Army Group, but most were no show status, or exit/enter at seperate non-overlapping periods, then that's fine?

Hi,

Yes thats right, its only the units on map that put a load on the system.

In fact on a map with terrible terrain you could proably get away with more as the route finding would be channeld down the road network, i.e. less searching across the whole map for a route.

Would it maybe pay dividends to have a 'long distance move' routine that uses a branch-and-node network based upon the map's road network for major moves, and then go to the regular path-finding when moving tactically?

[Arjuna]

FN,

Yes we experimented with that and wrote quite a lot of code to implement this on big maps. It wasn't that successful. There were a lot of cases or situations where it failed to provide an acceptable route. So we suspended further development in that direction. Another blind alley of R&D if you like. But It's something we could revisit.

[Prince of Eckmühl]

Hi Dave,

This one is 42km x 54km:



Do you think that it will bust the maps specs, or is it okay for me to proceed with it?

[Mac_MatrixForum]

ORIGINAL: Arjuna

Mac and Dan O,

This is a very complex issue and one that would probably bore the pants off most of our customers. What's more I really need a white board to explain it. The short answer though is we use as the basis the A* route calc method. Do a search on A* or AStar and you should find info on it. It's sometimes referred to as the marching ants algorythm as in its purest form it expands out from the start loc in all directions. If we just did that route calcs would take forever on large maps. So we apply a mountain of heuristics. We also have different heuristics for different route types - avoidance, asclusion, direct, shortest, covered etc.

Yeah, I guessed as much that you would be using A*. I've implemented it a few times in my life. I'm interested in how many routes do you have to calculate on average for one unit? Like do you try several different sets of heuristics for one plan? And how many nodes you have to visit to find one route? And how often do you need to reroute a given unit with no changes in orders? Can you reuse the old route and refine? Do you check every 5 mins of game time? How many routing calculations do you have per game loop or second? Do you have such statistics?

I think you manage very well. Players usually would and should expect near perfect routes from a computer but in real-life the commanders would rarely get it perfect anyway. The heuristics seem to work but no doubt they can be adjusted forever. And as long as the player can have input through intermediate waypoints it will work out, I think. And there is so many unknowns in a battlefield ...

When subordinate receives orders he bases his route on the boss's route if he is moving in formation with him. But he offsets this by the formation offset. However, to handle issues like not crossing over rivers etc, we apply a swag of heuristics to this as well. And then there's the issues of mixed mode movement, where we need to creqate effective start and end locs and RVs. Furhter we sometimes split the route for bridge building. We could talk for hours on this but hours I do not have right now. I hope this helps though.

Hierarchical planning I guessed too, it just makes sense. But I wonder if you use any kind of analysis of the maps during creation time to reduce calculations or is it even possible? Do you share all information between units of a given side about enemy positions etc.? Do you have to recalculate all routes whenever your side detects more enemy units?

I can imagine that you don't have the time to go through all the details, especially after launch, but the details are very interesting. BFTB is such a unique game. Thanks for making it [:)]

[Vincenzo_Beretta]

ORIGINAL: Arjuna

However, we've added a lot of code and processing to BFTB. It runs fine with the current constraints and scale. Increasing the map area, increased the area that has to be searched for route finding. If the total unit count is low, then it can be managed to a degree. If the unit count is high then it could slow things down to a crawl. Also if you retainthe same map constraints as we have now but increase the unit count dramatically, you increase the number of route calcs and other processing and this too may slow things down to a crawl.

Arjuna, since (in my total ignorance of anything programming-related [:)]) this does seem to be a number crunching limit... does the engine current take advantage of multi-threading?

[DanOppenheim]

Thanks for the information Arjuna.

I assumed it would be A* or some variation thereof. We use a version of D*, but that's more appropriate for our action-adventure games with a few agents than BftB with its hundreds.

[Arjuna]

Yes it does use multithreading. We use one thread for the UI and another for the AI plus we have four separate sound threads. In the future we would like to support multiple commands ( ie for coop play ) and have a separate thread per command. Then we could support bigger maps and more units. Ideally we can also then intoruduce load balancing across multiple PCs on a network. But that would require serious changes to the way we handle networked play. It would be a VERY BIG JOB.

[Arjuna]

DanO,

Please excuse my ignorance ( or is it the after effects of the wine I've been drinking at my daughters 21st birthday toninght ) but how does D* differ fromk A*.

[Arjuna]

ORIGINAL: Prince of Eckmühl

Hi Dave,

This one is 42km x 54km:



Do you think that it will bust the maps specs, or is it okay for me to proceed with it?

Hey is that the volcanoe you were asking Paul how to create? Nice. Did you do that in COTA MM or BFTB MM?

42 x 54 should be just OK.

[Arjuna]

Mac,

Too many complex questions for my tired brain to grapple with right now. I'll try and get to these later.

[DanOppenheim]

D* is basically A*, but it updates its path dynamically. If edges are added or removed or their value changed, then D* reevaluates only those bits of the path rather than the whole path. The original paper describing it is here, although there are better, updated versions if you have a hunt about. We use it because we've relatively small maps that are easily divisible into hierarchial nodes and we only need it for a few characters. I'm not sure it would scale too well if you have 100s of agents.

[Arjuna]

DanO,

Yeh that's the rub - the map size and number of units. We really need something that is lean and fast. We do however reuse sections of routes for certain purposes. For instance we store a copy of the boss route in the order it sends down to its subordinate. Then when the suboprdinate develops its plan or reassesses we sometimes use a section of the boss route - eg the subordinate is advancing to an RV point along the route before diverting off on its won. We determine the join loc for the subordinate, then copy the boss route between the join and RV and then determine a separate route from the RV to the suboridnate objective loc and then concatenate them to form one route. That way we only calc two short routes for the subordinate rather than one really big one.

[Prince of Eckmühl]

ORIGINAL: Arjuna

ORIGINAL: Prince of Eckmühl

Hi Dave,

This one is 42km x 54km:



Do you think that it will bust the maps specs, or is it okay for me to proceed with it?

Hey is that the volcanoe you were asking Paul how to create? Nice. Did you do that in COTA MM or BFTB MM?

42 x 54 should be just OK.

I did the altitude layers in CotA, but I've got it opening in the BftB scenario maker. I'll do the rest of the work in the Bulge map editor.

That blob in the upper-center is the Alban Hills that are southwest of Rome. I'm really interested in using BftB to explore hypotheticals as to what it would have taken for one side or the other to win a decisive victory. For the Axis, that means eliminating the Allied beach-head. And, of course, the Allies will have to seize those hills and threaten the Axis supply network centered in Rome, a development that should spell a quick end to the Gustav Line to the South.

For those interested in the campaign, here's an excellent place to start your study:

http://www.history.army.mil/books/wwii/ ... zio-fm.htm

[Arjuna]

Salerno and Anzio are two very good subjects for "what ifs". Both sides botched golden opportunities. But it was a real learning exercise, especially for the Allies. The capture of Rome on June 5th 1944 should have been a momentous event, but was overshadowed by an even more momentious event the next day - ie the DDay landings. Many forget that without the soak off effect ( over 20 German divisions ) that was created by the Italian campaign the DDay landings would have been a far more risky undertaking. The battle for Rome saw the Germans commit extra divisions south at a very critical time.

Good luck on this one.

[Prince of Eckmühl]

ORIGINAL: Arjuna

Good luck on this one.

What's luck got to do with it? [;)]