Improvements to the Speed of Calculations?

[Chuck2]

ORIGINAL: golden delicious

ORIGINAL: geozero

BTW - I used a Commodore which only booted up from a 5.25" floppy.

That's nothing. Before the ST we had a Commodore which loaded of cassette tapes. Those were the days.

You had a computer when you where 3-years-old? [&o]

[golden delicious]

ORIGINAL: Chuck2

You had a computer when you where 3-years-old?

I have two older brothers.

[CommC]

ORIGINAL: Erik Nygaard

So you think the game is simple?
Have you looked at a good researched scenario in the editor?
There are a lot of details there that the system needs to calculate for each side each turn,
especially if you play against the PO.
Believe me, there's nothing simplistic about TOAW.

Yeah, the large scenarios can be complex in that they include a lot of detail for the player to keep track of, but in terms or numbers of calculations, it is only a 2D game. 3d games require a lot more calculations and much more complex coding. TOAW3's code must be written in a very inefficient language or have major problems to take so long to make so few calculations.

[golden delicious]

ORIGINAL: CommC

Yeah, the large scenarios can be complex in that they include a lot of detail for the player to keep track of, but in terms or numbers of calculations, it is only a 2D game. 3d games require a lot more calculations and much more complex coding. TOAW3's code must be written in a very inefficient language or have major problems to take so long to make so few calculations.

The throwaway remark that it's "only a 2D game" really misses the level of depth in TOAW. For example, the replacement calculations for the larger scenarios have to consider the demans of thousands of units for around a dozen different items each. That is a hugely complicated calculation.

[geozero]

ORIGINAL: golden delicious

ORIGINAL: CommC

Yeah, the large scenarios can be complex in that they include a lot of detail for the player to keep track of, but in terms or numbers of calculations, it is only a 2D game. 3d games require a lot more calculations and much more complex coding. TOAW3's code must be written in a very inefficient language or have major problems to take so long to make so few calculations.

The throwaway remark that it's "only a 2D game" really misses the level of depth in TOAW. For example, the replacement calculations for the larger scenarios have to consider the demans of thousands of units for around a dozen different items each. That is a hugely complicated calculation.

It's not a throw away comment.

From this link http://www.cygnus-software.com/papers/x ... inity.html I give you the following:


Modern microprocessors, such as the Pentium 4 and the Athlon, can do floating point calculations at a tremendous speed. Floating point addition takes three to five clock cycles, so at 3 GHz a Pentium 4 can do about 600 million additions per second. Better yet, the floating point unit is heavily pipelined, meaning that many operations can be going on simultaneously. If your code is well designed and if there aren't too many dependencies, these processors can do a floating point add every cycle - so that 3 GHz Pentium 4 can actually do about 3 billion additions per second! That's pretty amazing considering that these calculations are being done with up to 19 decimal digits of accuracy. Wow.


Therefore, it comes down to a few points:

*** Well written and tight code.

*** A fast code language.

*** A fast processor.

*** Adequate RAM.

The first two are software dependent. Therefore, we can conclude that if TOAW is taking more than 30-60 seconds per turn, the code is bad, broken, or it's just not a fast language.

The last two points are user dependent. If you are not using a fast processor with adeuqte RAM your turns will simply take longer. Although it's a cliche, having the latest drivers for everything on your PC greatly helps.

SO, no, it's not a throw away comment. It's legit. Factual. Period.

[ralphtricky]

ORIGINAL: geozero

ORIGINAL: golden delicious

ORIGINAL: CommC

Yeah, the large scenarios can be complex in that they include a lot of detail for the player to keep track of, but in terms or numbers of calculations, it is only a 2D game. 3d games require a lot more calculations and much more complex coding. TOAW3's code must be written in a very inefficient language or have major problems to take so long to make so few calculations.

The throwaway remark that it's "only a 2D game" really misses the level of depth in TOAW. For example, the replacement calculations for the larger scenarios have to consider the demans of thousands of units for around a dozen different items each. That is a hugely complicated calculation.

That's not why it takes to long, that's a very quick calculation. The slow part is going over the entire map and figuring out how far away the point is from where it's supposed to reappear, friendly supply, cities, etc. It's in finding exactly the right place to put that unit![8D]

It's not a throw away comment.

From this link http://www.cygnus-software.com/papers/x ... inity.html I give you the following:


Modern microprocessors, such as the Pentium 4 and the Athlon, can do floating point calculations at a tremendous speed. Floating point addition takes three to five clock cycles, so at 3 GHz a Pentium 4 can do about 600 million additions per second. Better yet, the floating point unit is heavily pipelined, meaning that many operations can be going on simultaneously. If your code is well designed and if there aren't too many dependencies, these processors can do a floating point add every cycle - so that 3 GHz Pentium 4 can actually do about 3 billion additions per second! That's pretty amazing considering that these calculations are being done with up to 19 decimal digits of accuracy. Wow.

An interesting point that has no relevance for several reasons.

You can typically take advantage of the pipelining in 3D matrix operations and libraries, A typical program won't see much advantage because of it.

The minimum requirements aren't a P4

There are no floating point operations in TOAW III. None. Zip. Nada.

There aren't any memory allocations either, outside of the sound system.

Therefore, it comes down to a few points:

*** Well written and tight code.

Mostly, it is. This was designed many years ago, so there are some algorithms like the path-finding algorithm that need to be rewritten. It's not a bad algorithm, but there's a later one (A*) that's more efficient. The code is actually pretty tight for the most part. There were some design decisions that went for low memory usage instead of speed. There are local optimizations, like eliminating redundant checks, and moving temporary values out of a global array that can speed things up.[;)]

*** A fast code language.

C++, It's got most of the optimizations turned on, future upgrades will turn on the rest of them. C++, integer arithmetic, bitblts, no memory allocations. It doesn't get much faster than that.[:-]

*** A fast processor.

Read the minimum requirements.

*** Adequate RAM.

Without the sound ligrary, it only takes something like 24Meg.

The first two are software dependent. Therefore, we can conclude that if TOAW is taking more than 30-60 seconds per turn, the code is bad, broken, or it's just not a fast language.

It's also some incredibly complicated processing. Searching for a patch between hexes on a 300x300 grid isn't always quick, especially if there's an island involved. Switching to A* will help some with that, but there is still going to be a lot of processing happening.

The last two points are user dependent. If you are not using a fast processor with adeuqte RAM your turns will simply take longer. Although it's a cliche, having the latest drivers for everything on your PC greatly helps.

SO, no, it's not a throw away comment. It's legit. Factual. Period.

New paragraph...

Read the above inline comments. It's Legit, It's Factual, it has absolutely no relevance.[:'(]

The difference between 2D and 3D games isn't what you seem to think it is. I could easily slap a 3D front-end onto TOAW, the graphics card would take the brunt of the speed hit, you wouldn't notice a thing. The supply calculations are what take up the majority of the time. How many RTS games calculate supply lines the way that TOAW does?

Ralph Trickey

[geozero]

Fair enough.
 
On any given map 50% or more of the hexes are never used. 
 
Is there a way to avoid checking supply on hexes where no activity has taken place (i.e., no units have moved into or out out of)?  Seems that would speed things up.[:D]

[Szilard]

The optimal-reentry-point issue should be easy to fix. Delete "optimal", and just do something like: on/adjacent to unit's formation HQ; or if none, on/adjacent to a cooperative HQ close to evaporation position; or if none, on/adjacent to a nearby supply point; or if none, don't reconstitute.

You could argue that if the formation HQ happens to be 100's of km away, it wouldn't be realistic. But you can say the same thing about salvaged equipment from an evaporated unit being available as replacements for a distant, unrelated unit.

Supply paths bug me: in real life, there's nothing which corresponds to finding the optimal supply route to every point on the map. It'd be more realistic and also inherently faster to model something like (not necessarily optimal) supply lines connecting units and HQs. But I guess an easier fix might be to trace optimal routes to just on-map units, rather than to every single hex, which I assume is what happens now.

[ralphtricky]

There are a lot of things I can do. Probably the biggest help for the supply lookups is to look into rewriting it using the newer A* pathfinding algorithms. I'll have to write all that first, of course.[;)]

As a short term fix, I also might look into moving things out of this 300x300x48 array, and into a 300x300 array. Then things like clearing the array, etc. might be faster[;)]

[JAMiAM]

ORIGINAL: Szilard

The optimal-reentry-point issue should be easy to fix. Delete "optimal", and just do something like: on/adjacent to unit's formation HQ; or if none, on/adjacent to a cooperative HQ close to evaporation position; or if none, on/adjacent to a nearby supply point; or if none, don't reconstitute.

I don't know about that being an "easy" fix, since it would require a major departure from the current model of a 1-4 week window, and fixed position, for the reconstituted units appearing. Now, if sufficient equipment is available, then it is pulled, committed to a unit, and the unit is stuck on the scheduled reinforcements track to appear at a specific position, at some point in time 1-4 weeks away. To have it dependent upon "finding" an HQ to reappear next to, when the time comes for it to show up on the map, and failing that either redump the equipment into inventory, or continually be reassigned a new reconstitution point based on HQ's that may or may not still exist on the map, seems to me to be inherently more problematic.

[larryfulkerson]

ORIGINAL: ralphtrick
As a short term fix, I also might look into moving things out of this 300x300x48 array, and into a 300x300 array. Then things like clearing the array, etc. might be faster

If it's an array of chars, then if it's contiguous, then why not do a memove of '0' for 90000 chars. Would that be any faster?

[Szilard]

ORIGINAL: JAMiAM

ORIGINAL: Szilard

The optimal-reentry-point issue should be easy to fix. Delete "optimal", and just do something like: on/adjacent to unit's formation HQ; or if none, on/adjacent to a cooperative HQ close to evaporation position; or if none, on/adjacent to a nearby supply point; or if none, don't reconstitute.

I don't know about that being an "easy" fix, since it would require a major departure from the current model of a 1-4 week window, and fixed position, for the reconstituted units appearing. Now, if sufficient equipment is available, then it is pulled, committed to a unit, and the unit is stuck on the scheduled reinforcements track to appear at a specific position, at some point in time 1-4 weeks away. To have it dependent upon "finding" an HQ to reappear next to, when the time comes for it to show up on the map, and failing that either redump the equipment into inventory, or continually be reassigned a new reconstitution point based on HQ's that may or may not still exist on the map, seems to me to be inherently more problematic.

Fair enough. I'd be OK with just reconstituting at a supply point.

[a white rabbit]

ORIGINAL: golden delicious

ORIGINAL: geozero

BTW - I used a Commodore which only booted up from a 5.25" floppy.

That's nothing. Before the ST we had a Commodore which loaded of cassette tapes. Those were the days.

..16K Spectrum then upgraded to a 48K, coal fired

[golden delicious]

ORIGINAL: JAMiAM

I don't know about that being an "easy" fix, since it would require a major departure from the current model of a 1-4 week window, and fixed position, for the reconstituted units appearing. Now, if sufficient equipment is available, then it is pulled, committed to a unit, and the unit is stuck on the scheduled reinforcements track to appear at a specific position, at some point in time 1-4 weeks away. To have it dependent upon "finding" an HQ to reappear next to, when the time comes for it to show up on the map, and failing that either redump the equipment into inventory, or continually be reassigned a new reconstitution point based on HQ's that may or may not still exist on the map, seems to me to be inherently more problematic.

A quick thought here: you could bar reconstitution of component units of a formation which has lost its HQ, with the exception of the HQ itself. This serves to make HQs more valuable and also means that if a formation really gets smashed up it'll take a good deal longer to recover.

[ralphtricky]

ORIGINAL: larryfulkerson

ORIGINAL: ralphtrick
As a short term fix, I also might look into moving things out of this 300x300x48 array, and into a 300x300 array. Then things like clearing the array, etc. might be faster

If it's an array of chars, then if it's contiguous, then why not do a memove of '0' for 90000 chars. Would that be any faster?

[;)]

[ralphtricky]

ORIGINAL: a white rabbit

ORIGINAL: golden delicious

ORIGINAL: geozero

BTW - I used a Commodore which only booted up from a 5.25" floppy.

That's nothing. Before the ST we had a Commodore which loaded of cassette tapes. Those were the days.

..16K Spectrum then upgraded to a 48K, coal fired

..Altair 8800, built from a kit, fully loaded with 1024 Bytes of memory. Directly set the inputs using toggle switches, the only output is direct read of memory, or toggling the memory protect light (also played Mary had a Little Lamb on the AM radio.)

Top that[:D]

[Captain Cruft]

Here's an off the wall idea. I have no clue as to whether it's feasible or not.

Have a background thread which maintains a separate copy of the map array and unit data. Each action in the orders phase needs to update this copy, obviously. These updates would need to have a notion of the set of "affected hexes" and "affected units". Then, have the background thread continually doing the supply calcs and whatnot. So, come end of turn, it's probably about 95% of the way there already.

This is something like the way virtual memory works. Or database caching. We need to get away from only doing one thing at once.

Probably a nightmare to program mind you.

[ralphtricky]

ORIGINAL: Captain Cruft

Here's an off the wall idea. I have no clue as to whether it's feasible or not.

Have a background thread which maintains a separate copy of the map array and unit data. Each action in the orders phase needs to update this copy, obviously. These updates would need to have a notion of the set of "affected hexes" and "affected units". Then, have the background thread continually doing the supply calcs and whatnot. So, come end of turn, it's probably about 95% of the way there already.

This is something like the way virtual memory works. Or database caching. We need to get away from only doing one thing at once.

Probably a nightmare to program mind you.

There are a bunch of things I can do. I need to find the bottlenecks first. I hope to cut down the speed using some simple things first.

A thread is probably overkill unless I decide to use monte carlo simulation for the AI.

[Szilard]

ORIGINAL: ralphtrick

There are a lot of things I can do. Probably the biggest help for the supply lookups is to look into rewriting it using the newer A* pathfinding algorithms. I'll have to write all that first, of course.[;)]

Would that make such a big difference? I'd have thought it'd be the normal kind of thing where pruning the number of paths would give much bigger wins than optimizing individual path finding. Fun to play around with, anyway

[ralphtricky]

ORIGINAL: Szilard

ORIGINAL: ralphtrick

There are a lot of things I can do. Probably the biggest help for the supply lookups is to look into rewriting it using the newer A* pathfinding algorithms. I'll have to write all that first, of course.[;)]

Would that make such a big difference? I'd have thought it'd be the normal kind of thing where pruning the number of paths would give much bigger wins than optimizing individual path finding. Fun to play around with, anyway

Maybe not, but it's a lot more fun to play around with.
[;)]