Matrix Games Forums

Happy Easter!Battle Academy is now available on SteamPlayers compare Ageods Civil War to Civil War IIDeal of the week - An updated War in the East goes half Price!Sign up for the Qvadriga beta for iPad and Android!Come and say hi at Pax and SaluteLegends of War goes on sale!Piercing Fortress Europa Gets UpdatedBattle Academy Mega Pack is now availableClose Combat: Gateway to Caen Teaser Trailer
Forums  Register  Login  Photo Gallery  Member List  Search  Calendars  FAQ 

My Profile  Inbox  Address Book  My Subscription  My Forums  Log Out

Supply Revisions

 
View related threads: (in this forum | in all forums)

Logged in as: Guest
Users viewing this topic: none
  Printable Version
All Forums >> [New Releases from Matrix Games] >> World in Flames >> Supply Revisions Page: [1] 2 3   next >   >>
Login
Message << Older Topic   Newer Topic >>
Supply Revisions - 5/19/2010 4:34:24 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline
Up until now, MWIF has been using the supply routines from CWIF. Those routines are buggy, in that they are not current with modifications to the rules over the past 4-5 years. I also disapproved of their efficiency, since that will become vastly more important with the AIO exploring different moves for its units (and enemy units) and making judgments about how those moves affect supply. The AIO is likely to need to run the supply routines hundreds of times, not just a dozen or so as is true currently.

I have gotten some of the new routines to work: for determining all primary supply sources and making land connections from secondary supply sources to primary. Here are a couple of screen shots of one game example I am using for debugging purposes.

First the map. Note that the unit supply status is still being determined using the old CWIF routines.
---




Attachment (1)

_____________________________

Steve

Perfection is an elusive goal.
Post #: 1
RE: Supply Revisions - 5/19/2010 4:46:10 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline
Post 2 of 2 in the series.
---
Here is the new form I have created for displaying supply sources and paths. For now I have Theme Engine disabled, so there is a lot more gray in these screen shots than will appear in the released product.

The left screen shot shows all the secondary sources (there are more primary sources listed above Aachen). Notice all the cities that serve as secondary supply sources for the Germans. If I had clicked on one of them, the list of hexes on the right side of the screen shot would have shown the path from, say, Paris to a primary supply source city in Germany.

But I had clicked on Model, so that is the supply path shown. Model is visible in the insert map in the upper right corner (he is in hex [51, 50]. If you find the cursor's position in the insert map, that hex number is [44, 49], as indicated at the top of the screen. The search algorithm attempts to find a direct route to the nearest primary supply source and prefers rail lines over using up Basic Path hexes. But it does not backtrack on its path just to use a rail line - unless it has to. [44, 49] is the first hex the path enters that is not part of a rail line.

For the other two screens shots (von Bock and Manstein) you will probably want to refer to the full map shown in the previous post. Manstien is stacked under the Bf 109 fighter in the center of the insert map.




Attachment (1)

_____________________________

Steve

Perfection is an elusive goal.

(in reply to Shannon V. OKeets)
Post #: 2
RE: Supply Revisions - 5/19/2010 6:42:56 AM   
paulderynck


Posts: 3700
Joined: 3/24/2007
From: Canada
Status: offline
Some thoughts...

I wonder about preferring direct versus RR. Say you have storm and must go RR to a port and then overseas to a primary. Say the direct route is via one desert hex (RR is in that hex but no direct RR connection). You've already used up your supply range of two and won't have one more for the overseas part. I think it better to prefer RR first, no matter how circuitous, since the cost is zero per hex versus a minimum of one. Have you tested the algorithm for these more extreme cases? It would be interesting to see an example where the unit is not in supply.

Also here is an acid test: Pre-Barbarossa, Japan DoWs Persia and it aligns with the CW. Then Russia DoWs Japan and Russian units rush into Persia to assist in its defence. However Russian units that are not adjacent to Russia or to the Caspian (with a CONV in it, if playing LOS) are always out of supply, (except if given emergency HQ supply by an HQ within that same hex) because they can't trace into Allied hexes or vice versa until they are at war with Germany. Of note here is that your supply paths above begin with the hex the unit is in. But you trace from a unit to a supply source. So I might assume the algorithm would say the first hex of the route (the one occupied by the unit in question) is not OK, when in fact in this extreme example, those first hexes adjacent to Russia and the Caspian would be OK.

_____________________________

Paul

(in reply to Shannon V. OKeets)
Post #: 3
RE: Supply Revisions - 5/19/2010 3:18:41 PM   
micheljq


Posts: 654
Joined: 3/31/2008
From: Quebec
Status: offline
quote:

ORIGINAL: Shannon V. OKeets

Up until now, MWIF has been using the supply routines from CWIF. Those routines are buggy, in that they are not current with modifications to the rules over the past 4-5 years. I also disapproved of their efficiency, since that will become vastly more important with the AIO exploring different moves for its units (and enemy units) and making judgments about how those moves affect supply. The AIO is likely to need to run the supply routines hundreds of times, not just a dozen or so as is true currently.

I have gotten some of the new routines to work: for determining all primary supply sources and making land connections from secondary supply sources to primary. Here are a couple of screen shots of one game example I am using for debugging purposes.

First the map. Note that the unit supply status is still being determined using the old CWIF routines.
---


I think supply must be one of the single most important thing in this game.

< Message edited by micheljq -- 5/19/2010 7:49:19 PM >


_____________________________

Michel Desjardins,
"Patriotism is a virtue of the vicious" - Oscar Wilde
"History is a set of lies agreed upon" - Napoleon Bonaparte after the battle of Waterloo, june 18th, 1815

(in reply to Shannon V. OKeets)
Post #: 4
RE: Supply Revisions - 5/19/2010 6:43:20 PM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: paulderynck

Some thoughts...

I wonder about preferring direct versus RR. Say you have storm and must go RR to a port and then overseas to a primary. Say the direct route is via one desert hex (RR is in that hex but no direct RR connection). You've already used up your supply range of two and won't have one more for the overseas part. I think it better to prefer RR first, no matter how circuitous, since the cost is zero per hex versus a minimum of one. Have you tested the algorithm for these more extreme cases? It would be interesting to see an example where the unit is not in supply.

Also here is an acid test: Pre-Barbarossa, Japan DoWs Persia and it aligns with the CW. Then Russia DoWs Japan and Russian units rush into Persia to assist in its defence. However Russian units that are not adjacent to Russia or to the Caspian (with a CONV in it, if playing LOS) are always out of supply, (except if given emergency HQ supply by an HQ within that same hex) because they can't trace into Allied hexes or vice versa until they are at war with Germany. Of note here is that your supply paths above begin with the hex the unit is in. But you trace from a unit to a supply source. So I might assume the algorithm would say the first hex of the route (the one occupied by the unit in question) is not OK, when in fact in this extreme example, those first hexes adjacent to Russia and the Caspian would be OK.

But that is for overseas supply. What I was showing was for secondary to primary over land. In that case, there is no need to minimize the use of Basic path hexes.

For overseas rail paths from secondary to primary I am building 3 links: (1) land link from secondary to port, (2) overseas link from port to port, and (3) land link from port to primary. The algorithm actually does these in reverse, determining #3 first. And, as you note, it is important to find the path which uses the fewest number of basic path hexes for that link. I then store the # of basic path hexes needed into a list of sea areas that can trace a path to that port/link.

Expanding the overseas link to include other sea areas was fairly easy to code, and I already have that working. So, the second link from port to port is in place.

Lastly, I do the first land link, from a secondary to a port [that is what I am working on today]. That portion of the algorithm, 'knows' how many basic path hexes are going to be used linking through the port, sea areas, and back to the primary; which means when the secondary to port calculaion is performed, it knows how many basic path hexes it still has available to reach the port. Note that at that time it also knows the weather for the secondary supply source, so it knows the effect of weather on the number of basic path hexes it has available too.
===
Another major factor here is whether the secondary supply source is going to be used by a unit of the controlling major power or a cooperating country (major or minor). In those cases, it is important to know whether the primary supply source is controlled by the same major power as the secondary or by a coooperating country (and other variations on ownership of the primary and secondary). For example, a Hungarian unit in western France could trace a path to Paris, assuming Paris has been taken by the Germans. But if the Italians had taken Paris, then the Hungarians could not use Paris as a secondary supply source. For a German unit, which of the 2 major powers had taken Paris would be irrelevant.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to paulderynck)
Post #: 5
RE: Supply Revisions - 5/19/2010 7:18:08 PM   
Razz


Posts: 2517
Joined: 10/21/2007
From: CaLiForNia
Status: offline
Very interesting........

(in reply to Shannon V. OKeets)
Post #: 6
RE: Supply Revisions - 5/22/2010 5:05:37 PM   
morgil


Posts: 114
Joined: 5/9/2008
From: Bergen, Norway
Status: offline
Not sure if I understand how you are doing it, so I thought I should just add my input on how to. Feel free to lol at it

I was thinking to make supply a hex quality, much like control or weather is. And then you could show on the map with a button click what hexes are in supply for what nation, like you do with the control markers, except you also add one for each minor country in an alliance. You should also mark hexes that would be in supply, if they were in control, and hexes that would be in supply if a HQ was around. And a number indicating how many steps have been taken to be in supply.
This would have to be done once every time a hex changes control, and every time there is a weather change, unless you calculate for all weather types at once, and add that to the supplyindicator.
So there you would have a grid laid out to show where HQs would have to go to give supply, maybe if more than one HQ would be needed, if there exist chokepoints to cut supply to a HQ or unit, what hexes would, or not, be in supply given weather changes, etc.

The routine could be modified, so for every hex there is a path indicating its preferred supply route, its optimal route and such, and then you only need to calculate its supply if control or ZOC has changed in that path.

Dunno if this is a good idea or not, since I am absolutely clueless about writing code.

_____________________________

Gott weiss ich will kein Engel sein.

(in reply to Razz)
Post #: 7
RE: Supply Revisions - 5/22/2010 6:10:22 PM   
Taxman66


Posts: 132
Joined: 3/19/2008
Status: offline
I would guess that supply is way to dynamic to determine as a hex quality. Weather, and movement of 2nd supply sources (HQ), use of supply counters, emergency HQ supply means that you would be recalculating supply for a large number of hexes every time one of the above conditions changed.

_____________________________

"Part of the $10 million I spent on gambling, part on booze and part on women. The rest I spent foolishly." - George Raft

(in reply to morgil)
Post #: 8
RE: Supply Revisions - 5/22/2010 8:05:03 PM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline
quote:

ORIGINAL: Taxman66

I would guess that supply is way to dynamic to determine as a hex quality. Weather, and movement of 2nd supply sources (HQ), use of supply counters, emergency HQ supply means that you would be recalculating supply for a large number of hexes every time one of the above conditions changed.

Correct!

Moving a unit has the potential for changing supply for hundreds of hexes. It is bad enough that it can do that for dozens of units. And then there is the consideration of how many hexes there are on the map. Even excluding the all-sea hexes leaves tens of thousands. I do not want to have to update all those hexes everytime a unit moves.

< Message edited by Shannon V. OKeets -- 5/22/2010 8:06:02 PM >


_____________________________

Steve

Perfection is an elusive goal.

(in reply to Taxman66)
Post #: 9
RE: Supply Revisions - 5/23/2010 12:34:15 AM   
Taxman66


Posts: 132
Joined: 3/19/2008
Status: offline
It would be easier if supply was done at the begining of (sub) phase only... or after the expenditure of emergency HQ supply or a supply chit. That way you wouldn't have to refigure out supply each time a HQ moves.

I would bet this is the way its done in most games. It would be very easy to start the movement phase, figure that everyone is in supply then move a HQ and suddenly a bunch of units go out of supply before they get to move.

Unless I'm misremembering the 'when to calculate supply' rules. -- I haven't played in a long time, and when I did we didn't worry about the above situation.

_____________________________

"Part of the $10 million I spent on gambling, part on booze and part on women. The rest I spent foolishly." - George Raft

(in reply to Shannon V. OKeets)
Post #: 10
RE: Supply Revisions - 5/23/2010 1:40:40 AM   
ullern


Posts: 1752
Joined: 5/28/2006
Status: offline
quote:

ORIGINAL: Shannon V. OKeets

Up until now, MWIF has been using the supply routines from CWIF. Those routines are buggy, in that they are not current with modifications to the rules over the past 4-5 years. I also disapproved of their efficiency, since that will become vastly more important with the AIO exploring different moves for its units (and enemy units) and making judgments about how those moves affect supply. The AIO is likely to need to run the supply routines hundreds of times, not just a dozen or so as is true currently.

I have gotten some of the new routines to work: for determining all primary supply sources and making land connections from secondary supply sources to primary. Here are a couple of screen shots of one game example I am using for debugging purposes.



I think I have a pretty good idea about how you create the supply logic, and I like your solution. But this thing about "exploring different moves for its units (and enemy units)" I am not sure I understand what exactly you are trying to do.

I think that this is not really about moving for supply purposes but moving units in general. I have to admit I haven't read any details on how you plan to let the AIO move, but just tell me if I am off:

I think it's probably easy enough to prioritize which units to move if the side moving are attacking. Because in an attack the defense factors is known, and the AIO can run some sort of optimization routine to maximize its chance for success across all its attacks.

On the other end, I think that if nobody is attacking the situation is likely much harder to solve. Say Germany is fighting in the USSR, it's winter and snow, but the the USSR player is too weak or simply does not have enough white print yet to attack, so no side will attack in the snow. At the same time neither side has enough units to make a continues front all the way really, so both sides has some choices to make. And on what basis should the AIO prioritize to move which units where?
_ Some obvious choices is that the side with most units can try to creep through enemy lines. But for both sides the thing here is to try to take land or cut the supply of the opponent, while at the same time making sure that own freedom of movement is maximized, while opponent freedom of movement is minimized, and supply should hold,and there may be aircraft involved which should or shouldn't be overrun depending on whether the aircraft are mine or yours....

And on the bottom of this there is some computer AI that starts: say I move my units so there is an opening in the lines for the opponent 6-move ARM. The 6'move ARM may then move zero, 1, 2, 3, 4, 5 or 6 hexes into my territory next impulse, and he may go straight ahead or turn left or right at some point along that path. Would the AIO then evaluate the consequences for it's own and it's opponents both supply and later choices of movement for all these cases? Say that the AI has 10 units which could react to the 6 move ARM moves through. Then it could move none, any 1, any group of 2, 3, 4, 5, 6, 7, 8, 9 or all 10 units, each of which could be moved 1, 2, 3, 4, 5 or 6 hexes in any direction, which makes for an awful lot of possibilities for each unit - well actually just 7 choices for a 1-move GAR, but 127 choices for a 6 move ARM or MECH, but all the combinations here seems staggering, and by now we have still just evaluated the consequences of letting a single enemy unit move through the lines. Now let's evaluate the second one, or what about letting two enemy units move through my lines at the same time?

I have no idea if this is anything like what you plan to do or not. I am quite sure that todays computer can get through an awful lot of permutations by brute force. But for a front with maybe 300 units on each side where all units can move to an averagely 50 other hexes, all the ways the moves can be combined if you are going to think more than one step ahead and with multiple aspects to think of, both attack, control, supply, ZOC, victory cities, production, overrun moves and maybe more I forgot. This doesn't seem pretty.

I was just thinking that for an issue like supply calculating what the opponent actually may do may not be the best solution. Because considering all the permutation on how to move, and considering PARA-drops, invasions, partisans, reinforcements in cities you moved past but didn't take yet, and double impulses means there are that many choices that a more theoretical approach may be quite a bit more cost efficient. In general the best would be to give the AI some sort of idea of shape if it's area, and what shapes are good shapes and what are bad shapes. That might be hard too. For supply isn't the basic idea that you need to know whether or not the current supply chain is the single one possible or if there are two, or three or more? But I think it's possible to figure that out without considering where to the enemy may actually move.

Enough for now...

< Message edited by ullern -- 5/23/2010 1:46:23 AM >

(in reply to Shannon V. OKeets)
Post #: 11
RE: Supply Revisions - 5/23/2010 3:50:17 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: ullern

quote:

ORIGINAL: Shannon V. OKeets

Up until now, MWIF has been using the supply routines from CWIF. Those routines are buggy, in that they are not current with modifications to the rules over the past 4-5 years. I also disapproved of their efficiency, since that will become vastly more important with the AIO exploring different moves for its units (and enemy units) and making judgments about how those moves affect supply. The AIO is likely to need to run the supply routines hundreds of times, not just a dozen or so as is true currently.

I have gotten some of the new routines to work: for determining all primary supply sources and making land connections from secondary supply sources to primary. Here are a couple of screen shots of one game example I am using for debugging purposes.



I think I have a pretty good idea about how you create the supply logic, and I like your solution. But this thing about "exploring different moves for its units (and enemy units)" I am not sure I understand what exactly you are trying to do.

I think that this is not really about moving for supply purposes but moving units in general. I have to admit I haven't read any details on how you plan to let the AIO move, but just tell me if I am off:

I think it's probably easy enough to prioritize which units to move if the side moving are attacking. Because in an attack the defense factors is known, and the AIO can run some sort of optimization routine to maximize its chance for success across all its attacks.

On the other end, I think that if nobody is attacking the situation is likely much harder to solve. Say Germany is fighting in the USSR, it's winter and snow, but the the USSR player is too weak or simply does not have enough white print yet to attack, so no side will attack in the snow. At the same time neither side has enough units to make a continues front all the way really, so both sides has some choices to make. And on what basis should the AIO prioritize to move which units where?
_ Some obvious choices is that the side with most units can try to creep through enemy lines. But for both sides the thing here is to try to take land or cut the supply of the opponent, while at the same time making sure that own freedom of movement is maximized, while opponent freedom of movement is minimized, and supply should hold,and there may be aircraft involved which should or shouldn't be overrun depending on whether the aircraft are mine or yours....

And on the bottom of this there is some computer AI that starts: say I move my units so there is an opening in the lines for the opponent 6-move ARM. The 6'move ARM may then move zero, 1, 2, 3, 4, 5 or 6 hexes into my territory next impulse, and he may go straight ahead or turn left or right at some point along that path. Would the AIO then evaluate the consequences for it's own and it's opponents both supply and later choices of movement for all these cases? Say that the AI has 10 units which could react to the 6 move ARM moves through. Then it could move none, any 1, any group of 2, 3, 4, 5, 6, 7, 8, 9 or all 10 units, each of which could be moved 1, 2, 3, 4, 5 or 6 hexes in any direction, which makes for an awful lot of possibilities for each unit - well actually just 7 choices for a 1-move GAR, but 127 choices for a 6 move ARM or MECH, but all the combinations here seems staggering, and by now we have still just evaluated the consequences of letting a single enemy unit move through the lines. Now let's evaluate the second one, or what about letting two enemy units move through my lines at the same time?

I have no idea if this is anything like what you plan to do or not. I am quite sure that todays computer can get through an awful lot of permutations by brute force. But for a front with maybe 300 units on each side where all units can move to an averagely 50 other hexes, all the ways the moves can be combined if you are going to think more than one step ahead and with multiple aspects to think of, both attack, control, supply, ZOC, victory cities, production, overrun moves and maybe more I forgot. This doesn't seem pretty.

I was just thinking that for an issue like supply calculating what the opponent actually may do may not be the best solution. Because considering all the permutation on how to move, and considering PARA-drops, invasions, partisans, reinforcements in cities you moved past but didn't take yet, and double impulses means there are that many choices that a more theoretical approach may be quite a bit more cost efficient. In general the best would be to give the AI some sort of idea of shape if it's area, and what shapes are good shapes and what are bad shapes. That might be hard too. For supply isn't the basic idea that you need to know whether or not the current supply chain is the single one possible or if there are two, or three or more? But I think it's possible to figure that out without considering where to the enemy may actually move.

Enough for now...

Exploring all the combinations and permutations (order in which things occur) of moves is not my intention. However, I do intend to have the AIO examine the possibilities of cutting off enemy units from supply. For that purpose, the new supply routines record the supply paths for each unit. Furthermore, they record how many units are using each link in the supply chain.

The record keeping is done for both friendly and enemy units and is used for evaluating the 'value' of a hex in some instances. This is no different than what human players do when they notice a critical hex in the supply paths for many units.

Given a hex to attack/defend, then the question becomes which units are truly cut off from supply when a link is broken. Most of the time, an alternative supply path can be found. That is the point where I expect most of the supply recalculations will be done by the AIO. It's a significant number but doesn't have anything remotely close to having a factorial involved.

On the other hand, during the normal game play (regardless of mode of play: Internet, AIO, Solitaire, etc,) there is the question of redetermining supply dynamically as a player completes the move for each unit. The effects on supply of moving air and naval units is relatively rare and easily detected, given a knowledge of all the current supply paths in use and the units that are out-of-supply. Land movement is another ball of wax though. There the movement of an individual unit can have massive effects on both friendly and enemy units. Additionally, it isn't all that easy to determine when a move might put out-of-supply and isolated units back in supply.

Actually, the issue of how to deal with updating supply for units during land movement has been an open issue for me for over 4 years, a while I have made some progress in improving my understanding of the problem and possible solutions, I am not overwhelmingly confident that my current (envisioned) solution is best.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to ullern)
Post #: 12
RE: Supply Revisions - 5/23/2010 4:38:54 AM   
morgil


Posts: 114
Joined: 5/9/2008
From: Bergen, Norway
Status: offline

quote:

ORIGINAL: Taxman66

I would guess that supply is way to dynamic to determine as a hex quality. Weather, and movement of 2nd supply sources (HQ), use of supply counters, emergency HQ supply means that you would be recalculating supply for a large number of hexes every time one of the above conditions changed.


Hmm, I feel that supply is rather static, emergency HQ supply gives direct supply to specified units, supply counters makes the HQ a primary source, ie that hex turns into a primary supply source for the remainder of the turn, and calculate from there.
Movement of a HQ would necessitate recalculations, but you would only need to recalculate those hexes that was affected by the move, those that was marked as having supply because of a HQ.
Or you could do a bit of both.
You should get 3 possible states for a hex, Yes, No, and maybe. And then do calculations for the Noes when you conquer a hex, and the maybes when you move a HQ.

Or its a really bad idea..its too late to be certain

_____________________________

Gott weiss ich will kein Engel sein.

(in reply to Taxman66)
Post #: 13
RE: Supply Revisions - 5/23/2010 6:06:03 PM   
paulderynck


Posts: 3700
Joined: 3/24/2007
From: Canada
Status: offline

quote:

ORIGINAL: Taxman66

It would be easier if supply was done at the begining of (sub) phase only... or after the expenditure of emergency HQ supply or a supply chit. That way you wouldn't have to refigure out supply each time a HQ moves.

I would bet this is the way its done in most games. It would be very easy to start the movement phase, figure that everyone is in supply then move a HQ and suddenly a bunch of units go out of supply before they get to move.

Unless I'm misremembering the 'when to calculate supply' rules. -- I haven't played in a long time, and when I did we didn't worry about the above situation.

In WiFFE during land movement, you can move units that trace to an HQ, then move the HQ to put other land units in supply, and then move them. So supply needs to be able to change dynamically during the movement phase. This does happen reasonably frequently in our games.

_____________________________

Paul

(in reply to Taxman66)
Post #: 14
RE: Supply Revisions - 5/23/2010 6:12:31 PM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: morgil


quote:

ORIGINAL: Taxman66

I would guess that supply is way to dynamic to determine as a hex quality. Weather, and movement of 2nd supply sources (HQ), use of supply counters, emergency HQ supply means that you would be recalculating supply for a large number of hexes every time one of the above conditions changed.


Hmm, I feel that supply is rather static, emergency HQ supply gives direct supply to specified units, supply counters makes the HQ a primary source, ie that hex turns into a primary supply source for the remainder of the turn, and calculate from there.
Movement of a HQ would necessitate recalculations, but you would only need to recalculate those hexes that was affected by the move, those that was marked as having supply because of a HQ.
Or you could do a bit of both.
You should get 3 possible states for a hex, Yes, No, and maybe. And then do calculations for the Noes when you conquer a hex, and the maybes when you move a HQ.

Or its a really bad idea..its too late to be certain

The problem is that a large group of units may have supply through a single hex (think of the combat in the USSR around the Urals). If that supply gets cut by the loss of a single hex, then there are, say, a dozen units out of supply. Whenever a unit moves there is the possibility that those units would have their supply restored. For example, it is possible to cut supply with a Zone of Control over an empty hex that is controlled by the enemy. So land movement by either side could affect the supply status of the cut off units.

This situation gets worse when the task is to maintain the supply status of hexes.
===
But this discussion has made me think that perhaps I should record hexes that could never have supply unless a HQ is close. Most of Siberia, Africa, Australia, and South America could qualify for that distinction. By eliminating such hexes from consideration as being part of a supply path, might make the search routine more efficient. That is just a recent thought (1 minute old), and my first impulse is to believe maintaining those hexes could well offset any benefit in reduced processing time from the increased knowledge about the search space. For now, I think I'll go with the more straight-forward solution and keep this idea in reserve in case difficulties arise in the future.
===
Getting nack to the idea of displaying hex supply status to the players. I could use the same (or a similar) graphic as used for hex control. So the coding of the new information display wouldn't be a big problem. But the value of the information to the player seems to me to be minimal. Certainly during the decades that WIF has been played over-the-board such a feature has not been available.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to morgil)
Post #: 15
RE: Supply Revisions - 5/23/2010 10:20:42 PM   
Incy

 

Posts: 296
Joined: 10/25/2003
Status: offline
You could always calculate supply 'backwards'. I.e. start with primary sources, and then recursivly add all adjacent hexes and test them. This way you'd never test those far-off hexes.

Also, you should probably do one supply calculation for all secondary supply sources first, creating a list of of valid ones. You would also manitain a list of all the hexes secondary supplies trace through (and all secondary sources a secondary source traces via).

'normal' supply checks would then be a matter of checking for a path of up to 4 hexes to any nearby secondary supply hex.

Whenever supply status might change (a hex changes control, ZOC blocking a hex, secondary source moves, etc), all that needs to be done is:
1. lookup if any secondary traces trough the affected hex. If so, recalculate paths for those
2. once that is resolved, recalculate any normal units within 4 hexes of a secondary that has been moved or has been disabled/enabled by the previous test
3. recalculate any normal unit within 4 hexes of the changed hex

Most supply-affecting moves will not trigger step 1 or 2, so only step 3 (which should be very cheap) would have to be done.

(in reply to Shannon V. OKeets)
Post #: 16
RE: Supply Revisions - 5/24/2010 6:16:03 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: Incy

You could always calculate supply 'backwards'. I.e. start with primary sources, and then recursivly add all adjacent hexes and test them. This way you'd never test those far-off hexes.

Also, you should probably do one supply calculation for all secondary supply sources first, creating a list of of valid ones. You would also manitain a list of all the hexes secondary supplies trace through (and all secondary sources a secondary source traces via).

'normal' supply checks would then be a matter of checking for a path of up to 4 hexes to any nearby secondary supply hex.

Whenever supply status might change (a hex changes control, ZOC blocking a hex, secondary source moves, etc), all that needs to be done is:
1. lookup if any secondary traces trough the affected hex. If so, recalculate paths for those
2. once that is resolved, recalculate any normal units within 4 hexes of a secondary that has been moved or has been disabled/enabled by the previous test
3. recalculate any normal unit within 4 hexes of the changed hex

Most supply-affecting moves will not trigger step 1 or 2, so only step 3 (which should be very cheap) would have to be done.


This is, more or less, what I am doing with my revisions to the supply routines.

What I think you have underestimated though is secondary supply sources that become 'unviable' during movement (mostly land but also due to air and naval moves at times). A simple example is the loss of supply through the Italian Coast which would put all Axis units in North Africa out-of-supply (the reverse is also possible where they are all suddenly in supply. And just because one secondary supply source becomes unviable doesn't mean that an alternative can't be found.

As I've said, keeping track of this for units is burdensome, and to do so for hexes would be more so.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to Incy)
Post #: 17
RE: Supply Revisions - 5/25/2010 1:51:29 AM   
Neilster


Posts: 2235
Joined: 10/27/2003
From: Hobart, Tasmania, Australia
Status: offline
The power of recursion! It's good to see Incy giving input here too.

Cheers, Neilster

(in reply to Shannon V. OKeets)
Post #: 18
RE: Supply Revisions - 5/25/2010 3:46:30 PM   
SamuraiProgrammer

 

Posts: 338
Joined: 10/17/2004
From: Paducah, Kentucky
Status: offline
Steve,

Have you considered the following:

You will carry 2 supply status flags for each hex (Current and New)
You will carry a flag to see if any changes have been made to supply Status

Reset SupplyStatusChange flag
Start at the hex where the unit moved from
-- Check to see if absence of this unit changed supply status for that hex
--- If so,
---- Set NewSupplyStatus
---- SetSupplyStatus flag
-- Check to see if absence of this unit changed supply status for adjacent hexes
--- If so,
---- Set NewSupplyStatus
---- Set SupplyStatusChange flag
-- If SupplyStatusChange flag is set iterate hexes adjacent to hexes just checked looking for changes until no changes are made


Repeat the entire process except you start from the hex where the unit ended up in and check to see if it being there makes a change.

This should minimize the impact of the calculations on performance.
This should be done every hex the unit moves IF it can affect supply. It should not be delayed until movement of the unit is finished.

Questions, Comments, Insults?








_____________________________

Bridge is the best wargame going .. Where else can you find a tournament every weekend?

(in reply to Neilster)
Post #: 19
RE: Supply Revisions - 5/25/2010 9:13:38 PM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: SamuraiProgrammer

Steve,

Have you considered the following:

You will carry 2 supply status flags for each hex (Current and New)
You will carry a flag to see if any changes have been made to supply Status

Reset SupplyStatusChange flag
Start at the hex where the unit moved from
-- Check to see if absence of this unit changed supply status for that hex
--- If so,
---- Set NewSupplyStatus
---- SetSupplyStatus flag
-- Check to see if absence of this unit changed supply status for adjacent hexes
--- If so,
---- Set NewSupplyStatus
---- Set SupplyStatusChange flag
-- If SupplyStatusChange flag is set iterate hexes adjacent to hexes just checked looking for changes until no changes are made


Repeat the entire process except you start from the hex where the unit ended up in and check to see if it being there makes a change.

This should minimize the impact of the calculations on performance.
This should be done every hex the unit moves IF it can affect supply. It should not be delayed until movement of the unit is finished.

Questions, Comments, Insults?








While I had to read your post twice to figure out what you were driving at, I agree. And it is very helpful.

Leaving aside the issue of flags, et al, it is easy enough to see if the presence/absence of a unit in a hex affects supply. Clearly any unit (aside from HQs) moving around behind its own frontline will have no effect on the supply status of any units anywhere. Let's call this Check #1.

As for possibility of cutting supply, that can be easily checked by comparing a hex whose supply status has changed because it failed Check #1. I'll simply search for the hex in the list of all the hexes used by enemy units for supply. That's not as long a list as you might think, since I'm keeping track of supply paths as links. Many units will be using the same link, so the number of links is likely to be a couple of dozen - even for the frontline in the USSR at the height of the conflict there.

If the change in supply status might restore supply to some units, well, that's not too bad either since I only have to examine out of supply units (a couple of dozen at most?).
---
I have overseas supply for secondary supply sources working and today I''ll code all tertiary supply sources.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to SamuraiProgrammer)
Post #: 20
RE: Supply Revisions - 5/25/2010 9:37:37 PM   
SamuraiProgrammer

 

Posts: 338
Joined: 10/17/2004
From: Paducah, Kentucky
Status: offline
Sorry I didn't write it a little more clearly... it is difficult because it is a recursive process.

Honestly, I haven't followed this thread that closely so I may show that I am an idiot... I also realize it may be a processing time vs. memory consumption issue. So if this is moot, no problem.

I think my poor explaination has kept a key point from being conveyed. I will come at it from another direction.

I wonder if it is fruitful to carry a list of supply paths. This method allows each hex to know whether it is in supply or not. The units simply 'ask' the hex. Furthermore, this may be a little more graceful (and quick) in handling situations where a supply line is invalidated but there is another valid supply line to replace it.

The original algorithm came from letting supply 'organically ooze' from supply points. But when you have to do that every time something moves, it is ineffective. When a unit moves, two things can happen.


_____________________________

Bridge is the best wargame going .. Where else can you find a tournament every weekend?

(in reply to Shannon V. OKeets)
Post #: 21
RE: Supply Revisions - 5/25/2010 9:43:59 PM   
SamuraiProgrammer

 

Posts: 338
Joined: 10/17/2004
From: Paducah, Kentucky
Status: offline
(sorry pressed the wrong button - adding another message instead of editing for those who get this in email or digest)

A) moving out of the hex affects supply
B) moving into the hex affects supply.

If there are other units already affecting supply so that neither of these occur, then nothing changes and supply is the same.

If either of these occur, you want the changes to cascade hex by hex (or sea zone as the case may be). Fortunately, this only has to continue cascading as long as there are changes being made. As each hex is tested, if it's status changes, then any hexes (or sea zones as the case may be) it touches that have not already been checked or are not checked during this iteration, will need to be checked on the next iteration. This iterative process (not really recursive as I said before) will allow the changes to the ability of a hex to pass on supply ooze until the situation is not changing any further.

I may be oversimplifying the problem and it may be that you already get what I am thinking. You may have found the dividing line where a hybrid of the two solutions is most efficient.

Good Luck and Happy to have helped.


_____________________________

Bridge is the best wargame going .. Where else can you find a tournament every weekend?

(in reply to SamuraiProgrammer)
Post #: 22
RE: Supply Revisions - 5/25/2010 10:50:12 PM   
Incy

 

Posts: 296
Joined: 10/25/2003
Status: offline
You don't have to check along the way. Just the start hex, end hex, and any hex that changed control.
(The rules don't have any supply requirements WHILE moving)

(in reply to SamuraiProgrammer)
Post #: 23
RE: Supply Revisions - 5/25/2010 11:45:51 PM   
Taxman66


Posts: 132
Joined: 3/19/2008
Status: offline
You also have the problem that it is not the hex that is drawing supply but the untis in the hex. You can easily have a situation where the hex would be in supply for one type of unit but not another. Frex: A GE unit in a hex is being supplied through an IT HQ; But a Finnish unit in the same hex would be OOS.

_____________________________

"Part of the $10 million I spent on gambling, part on booze and part on women. The rest I spent foolishly." - George Raft

(in reply to Incy)
Post #: 24
RE: Supply Revisions - 5/26/2010 12:16:18 AM   
Incy

 

Posts: 296
Joined: 10/25/2003
Status: offline
For the list containing paths supply moves through, I think it would be best if it contains a list of all units tracing through the hex.

Possible memory structure:

Map supply_paths
key: hex_id/seazone_id
value: list of units tracing through that hex

You would only add the hexes to the next secondary/primary source. So a normal unit would only be in the list for up to 4 hexes. You would also have:

Map unit_supply_path
key: target_id (for primary or secondary source)
value: list of units tracing to target

You'd have a list of secondary supply sources that are OOS
You'd have a list of units to have their supply recalculated.

The algoritm would be:
after unit move completed
for the start hex, check if it now empty and contains an enemy ZOC.
If so, call searchSupplyMap (hex_id, ZOC_nationality)
for any hex which control was changed
call searchSupplyMap (hex_id, null) (no nationality because all units on other side will lose supply)
for any hex adjacent to end hex and not containing a land unit
if endhex didn excert ZOC and now excerts ZOC
call searchSupplyMap (hex_id, ZOC_nationality)

for each unit in recalculate_list that is a secondary source
delete all entries for it from Map supply_path 
recalculate supply path
if path found, add path to Map supply_path 
else set out of supply, 
lookup all units tracing to it in Map unit_supply_path,
add these to recalculate_list

In case of chaining secondary sources you might have to repeat this step until no change happens.

for each unit in recalculate_list that is not a supply source
delete all entries for it from Map supply_path 
recalculate basic supply path (max 4 hexes except for overseas paths)
if path found, add path to Map supply_path 
else set out of supply


function searchSupplyMap (hex_id, ZOC_nationality)
{
lookup hex_id in Map supply_path
for each entry, check if at war with ZOC_nationality.
If true, add unit_id to recalculate_list,
}

Finally, you'll need to check for units put back in supply, which I think is harder. Potentially a secondary source in siberia might be put back in supply by a hex in poland opening, and the path doesn't exist so it's not in any list.

I think the best algorithm for this is to check all hexes that have become available and try to 'expand the suply grid' into any new opening.

for each hex that changed control, and for the end hex if it was empty of landunits but now isn't and is in enemy ZOC 
attempt to trace a rail path FROM this hex along a shotest possible route:
variable LENGHT holds the number of non-rail hexsides crossed in this path
List tested holds allready tested hexes
create a Map supplyTest
add the hex_id of the tested hex to the map, with LENGHT as the value
for each hex in Map supplyTest
for each adjacent hex not in list tested
if adjacent hex can trace to tested_hex and is rail hexside, add to Map supplyTest with same lenght
if adjacent hex can trace to tested_hex and is not rail hexside, add to Map supplyTest with lenght = lenght+1 (+2 for desert), unless lenght now is 5
if there are units in hex, and lenght <= supply path lenght, and units are OOS and can cooperate, set units in supply
add to list tested

if checked hex doesn't have a primary path, attemt to trace a basic path to a secondary source.
same algorithm as above, except lenght is always incremented regardless of rail.




(in reply to Incy)
Post #: 25
RE: Supply Revisions - 5/26/2010 2:14:21 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: Taxman66

You also have the problem that it is not the hex that is drawing supply but the untis in the hex. You can easily have a situation where the hex would be in supply for one type of unit but not another. Frex: A GE unit in a hex is being supplied through an IT HQ; But a Finnish unit in the same hex would be OOS.

What you said here is a key point about the hopelessness of maintaining the supply status of eaach hex on the map.

Even if we are just talking about the German player, some the units that he controls may be in supply and others in the same hex out of supply because of the supply rules. A simple example is a Rumanian city being a primary supply source for a Rumanian unit while a German unit sitting in the city could be out of supply.

_____________________________

Steve

Perfection is an elusive goal.

(in reply to Taxman66)
Post #: 26
RE: Supply Revisions - 5/26/2010 2:21:57 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline

quote:

ORIGINAL: Incy

For the list containing paths supply moves through, I think it would be best if it contains a list of all units tracing through the hex.

Possible memory structure:

Map supply_paths
key: hex_id/seazone_id
value: list of units tracing through that hex

You would only add the hexes to the next secondary/primary source. So a normal unit would only be in the list for up to 4 hexes. You would also have:

Map unit_supply_path
key: target_id (for primary or secondary source)
value: list of units tracing to target

You'd have a list of secondary supply sources that are OOS
You'd have a list of units to have their supply recalculated.

The algoritm would be:
after unit move completed
for the start hex, check if it now empty and contains an enemy ZOC.
If so, call searchSupplyMap (hex_id, ZOC_nationality)
for any hex which control was changed
call searchSupplyMap (hex_id, null) (no nationality because all units on other side will lose supply)
for any hex adjacent to end hex and not containing a land unit
if endhex didn excert ZOC and now excerts ZOC
call searchSupplyMap (hex_id, ZOC_nationality)

for each unit in recalculate_list that is a secondary source
delete all entries for it from Map supply_path 
recalculate supply path
if path found, add path to Map supply_path 
else set out of supply, 
lookup all units tracing to it in Map unit_supply_path,
add these to recalculate_list

In case of chaining secondary sources you might have to repeat this step until no change happens.

for each unit in recalculate_list that is not a supply source
delete all entries for it from Map supply_path 
recalculate basic supply path (max 4 hexes except for overseas paths)
if path found, add path to Map supply_path 
else set out of supply


function searchSupplyMap (hex_id, ZOC_nationality)
{
lookup hex_id in Map supply_path
for each entry, check if at war with ZOC_nationality.
If true, add unit_id to recalculate_list,
}

Finally, you'll need to check for units put back in supply, which I think is harder. Potentially a secondary source in siberia might be put back in supply by a hex in poland opening, and the path doesn't exist so it's not in any list.

I think the best algorithm for this is to check all hexes that have become available and try to 'expand the suply grid' into any new opening.

for each hex that changed control, and for the end hex if it was empty of landunits but now isn't and is in enemy ZOC 
attempt to trace a rail path FROM this hex along a shotest possible route:
variable LENGHT holds the number of non-rail hexsides crossed in this path
List tested holds allready tested hexes
create a Map supplyTest
add the hex_id of the tested hex to the map, with LENGHT as the value
for each hex in Map supplyTest
for each adjacent hex not in list tested
if adjacent hex can trace to tested_hex and is rail hexside, add to Map supplyTest with same lenght
if adjacent hex can trace to tested_hex and is not rail hexside, add to Map supplyTest with lenght = lenght+1 (+2 for desert), unless lenght now is 5
if there are units in hex, and lenght <= supply path lenght, and units are OOS and can cooperate, set units in supply
add to list tested

if checked hex doesn't have a primary path, attemt to trace a basic path to a secondary source.
same algorithm as above, except lenght is always incremented regardless of rail.





Your's was a long post I don't have the mental clarity to read through it clearly at the moment. I believe the code I have written does most of what you say, although I am not maintaining a supply status for each hex.

What I think is a quick and simple solution for re-determining supply is to check all the previous supply paths. That is done working backwards from the list of primary supply sources, secondary, tertiary, and lastly units. In the middle of that are the calculations about overseas supply.

I'm keeping a list of units supplied by each link, so if a link goes bad for some reason or another, I'll know immediately which units need to have their supply status determined afresh.

The place where this might not work so well is when the weather changes, reducing the basic supply path range, which can render a number of links infeasible.



_____________________________

Steve

Perfection is an elusive goal.

(in reply to Incy)
Post #: 27
RE: Supply Revisions - 5/26/2010 6:00:42 PM   
Incy

 

Posts: 296
Joined: 10/25/2003
Status: offline
The algorithm doesn't try to maintain the supply status of every supplied hex.
It just remembers actually traced supply paths.

The only list of hex status it has is a temporary list whenever a new hex gains supply. This is because it tries to expand 'backwards' all possible paths through the newly supplied hex, to see if any OOS units can now be supplied this way.

btw, you could split the stored list of traced supply paths by lenght.
one list for paths requiring 2 or less supply range, one for paths requiring 3, and one for paths requiring 4.
This approuach can get complex for chained routes involving several weather zones, though.

You may also need to modify the 'reconnect' part of your algorithm (the part that checks if supply has been reaquired) to have it try to shorten paths that requires 3 or 4 hexes. Or else a path that previously required 3 but now has a lenght 2 path available would be calculated to be OOS in rain.

If you can't make the algorithm work independent of weather changes you must recalculate all supply paths from scratch every time the weather changes. This might be acceptable, though.

(in reply to Shannon V. OKeets)
Post #: 28
RE: Supply Revisions - 5/26/2010 6:03:11 PM   
Incy

 

Posts: 296
Joined: 10/25/2003
Status: offline
btw, let me know if you want me to work more on the supply algorithms. You can post me the relevant code you already have, and I can make suggestions, or at least write pseudo-code more similar to your preferred language/coding convention

(in reply to Incy)
Post #: 29
RE: Supply Revisions - 5/27/2010 8:02:17 AM   
Shannon V. OKeets

 

Posts: 17933
Joined: 5/19/2005
From: Honolulu, Hawaii
Status: offline
quote:

ORIGINAL: Incy

btw, let me know if you want me to work more on the supply algorithms. You can post me the relevant code you already have, and I can make suggestions, or at least write pseudo-code more similar to your preferred language/coding convention

Thanks for the offer.

As of right now the new supply routines are over 6300 lines of code - probably not a good idea to post them.

I'll remember your offer if I become puzzled with what I am coding for supply. For right now, I am stepping the code through the routines that I have written to validate that they are performing as intended. Slow going but very informative. Did you know the Japanese controlled sea areas can serve to transmit supply for German units most of the time? Not likely to occur but the rules permit that to happen.

< Message edited by Shannon V. OKeets -- 5/27/2010 8:03:00 AM >


_____________________________

Steve

Perfection is an elusive goal.

(in reply to Incy)
Post #: 30
Page:   [1] 2 3   next >   >>
All Forums >> [New Releases from Matrix Games] >> World in Flames >> Supply Revisions Page: [1] 2 3   next >   >>
Jump to:





New Messages No New Messages
Hot Topic w/ New Messages Hot Topic w/o New Messages
Locked w/ New Messages Locked w/o New Messages
 Post New Thread
 Reply to Message
 Post New Poll
 Submit Vote
 Delete My Own Post
 Delete My Own Thread
 Rate Posts


Forum Software © ASPPlayground.NET Advanced Edition 2.4.5 ANSI

0.117