telengard
Member
That would be excellent if you could share that, thanks! And yeah, my work has periodic surges and my free time drops quite a bit. Hopefully things will cool down for you.
I believe if you click Resources on the menu bar at the top you will find it there.@ScottKittyHawk any chance you could share your python code here?
You are right, I was confusing it with another python program that he had posted there. My mistake.Thanks @DougRim, I did check there and I don't see it. Since 1/1/22 there are 5 resources there, none seem to be the python code for extracting the LOSdata from the vassal maps.
No rush at all Doug, and thank you. Hope your power comes back soon!I can answer some of those questions by I am without power at present due to a storm. Will get back to you on this as soon as possible.
In the VASL source code on Github look for src/VASL/LOS/Map/Map.java, specifically the method LOS() which begins around line 880. This is triggered by a call from src/VASL/build/module/map/VASLThread.doLOS().The one thing I haven't been able to locate in the VASL tree is exactly the code where LOS is calculated between 2 hexes. There's a lot of classes and layers.
Map.LOS() cited above calls applyLOSRules() which in turn calls a lot of methods begining with check. . . . . These methods (or those that they in turn call) usually contain code that excludes origin/target hexes.I have LOS working from center of hex to other center of hex, but I need to not include the originating hex and destination hex. I can do this with math (using the pixel data in LOSData), but I thought I'd check out the Java code that does it.
Terraintypes are defined in the SharedBoardMetadata.xml file which is located in the dist/boardData directory. See lines 1100 and followingI also couldn't figure out where the terrain types were defined in the VASL code and kinda figured it out empirically by cross referencing the pixel location to the .gif file. I found an enum, but it doesn't match up to the numbers in LOSData (e.g. 60 decimal for Woods).
Let me know which parts above are not clear and I will elaborate further.If anyone is interested in the code I can post it. My target is ASLSK, so I ignore elevation, etc and just check the terrainType. At some point I will add that too though, as well as hinderances.
Thank you Doug, super helpful! Especially the terrainTypes. I was looking all over the code, so in the totally wrong place!In the VASL source code on Github look for src/VASL/LOS/Map/Map.java, specifically the method LOS() which begins around line 880. This is triggered by a call from src/VASL/build/module/map/VASLThread.doLOS().
Map.LOS() cited above calls applyLOSRules() which in turn calls a lot of methods begining with check. . . . . These methods (or those that they in turn call) usually contain code that excludes origin/target hexes.
Terraintypes are defined in the SharedBoardMetadata.xml file which is located in the dist/boardData directory. See lines 1100 and following
Let me know which parts above are not clear and I will elaborate further.
Doug
I haven't taken a super-close look at your code, but you could calculate all this stuff once, then cache it somewhere (a SQLite database would probably be best), which would give you a massive speed-up when processing multiple boards.it takes a LONG time to run (on board y it takes over 15 hours).
You should put this up online somewhere - I'm sure there are a few of us who would be interested in taking a look. I mulled over doing something similar once, but I value my sanity...My ASL computer AI program is coming along great!
15 hours has got to hurt, every time you make a change. I started on mainframe batch systems, so I know the feeling...It's just this one time pass to generate the data that is such a long hit.
You're checking pixel colors along the LOS, right? So, you just figure out the angle the LOS takes to the hex on the other board, do your checks along that LOS, then switch to the other board and continue checking there...? If you pre-calculate the Bresenham points, you could probably do this on-demand.I haven't figured out how I will do multi-mapboards though. Ideally I could just utilize the individual outputs of each map, but there it's the connections between the 2 maps that wouldn't be covered.
Looks nice. I automate VASSAL from vasl-templates, so I had visions of the AI doing something similar to actually move the counters on the board. Something that cool, I don't think people would care if it didn't play all that well...Here's a screen grab of both sides
When there is a bug yeah, it stinks. When adding Brush support I let it run and of course there was a syntax error after writing it out. The script is such now that I can test with only a few entries and ensure the writing out logic works at least.15 hours has got to hurt, every time you make a change. I started on mainframe batch systems, so I know the feeling...
Yes, I'm checking terrain type (colors essentially) of the points along the LOS via Bresenham for every unique combo of hex to hex. The output for a single combo would look like this, in this case from hex A1 to Y1 on board yYou're checking pixel colors along the LOS, right? So, you just figure out the angle the LOS takes to the hex on the other board, do your checks along that LOS, then switch to the other board and continue checking there...? If you pre-calculate the Bresenham points, you could probably do this on-demand.
Thanks! I think the console interface scares folks off, but I'm used to it, and it is fully functional with no fuss and allows me to use the physical game itself. I'm still working on how to handle user choice. All of my games using this engine present a list and the player chooses a number which maps to the action. But in this game, the number of actions gets out of control when you consider all of the possible combinations for some things (like moves (normal, assault, double time, smoke) - and who is moving and to where), so I havea little meta language for inputting moves, like MA1A2, which would move all units in A1 to A2, if the action doesn't exist, it just asks again. I do support having the letter ids, leader names, etc for unique unit identification, but it makes setup, etc much longer as I have to dig specific counters out (the screenshot above doesn't show the letters, just the status to uniquely identify units).Looks nice. I automate VASSAL from vasl-templates, so I had visions of the AI doing something similar to actually move the counters on the board. Something that cool, I don't think people would care if it didn't play all that well...
It seems like you're thinking of how to handle LOS that spans 2 boards, but why not think of it as just one map...? Hexes would need to include the board number as part of their address, but otherwise everything stays the same.The issue I'm trying to figure out is to handle what is shown in the attached picture. The LOS in the red is the issue. I don't calculate the LOS from that point to the edge of the cardboard. I could probably store that though with like a "pretend" endpoint. The blue LOS I don't think will be an issue as it is a seamless continuation.
Yah, there's no chance of that I wrote a wrapper Java program that loads the VASSAL JAR, and then just calls the functions directly in that.I was thinking of the same thing, e.g. how to integrate something like this into Vassal and had asked on their forums if there was a way to do this via hooking or a plug-in interface.
Exactly, yeah. I'd like to try having to process combined boards and use the individual boards as laid out for the scenario. If I end up porting to C (which is starting to seem likely) this may not be too much of a concern. I have a feeling it is going to be WAY faster. My original AI engine years ago was in python and it was soooo slow. Porting to C++ increased performance dramatically.It seems like you're thinking of how to handle LOS that spans 2 boards, but why not think of it as just one map...? Hexes would need to include the board number as part of their address, but otherwise everything stays the same.
But the combinatorial explosion will kill ya. Doing 2 boards will take a lot longer than 30 hours - back of the envelope suggests around 70, which is unworkable.
Unless I'm misunderstanding, I think I do that now. Starting from say AA4, if it finds LOS is blocked at any point along the line, it stops.One thing that immediately jumps out to me is that if the code determines that the LOS marked in red below is blocked, it still checks all the other ones marked in blue, even though it's obviously pointless. There's a huge saving there, if you can avoid checking LOS for such hex pairs. Even better, these are increasingly longer-range LOS's, which take longer to check, so you're saving yourself even more work.
View attachment 22344
The grain hex determination suffers from the same logic the intersected hexes did, it doesn't handle straddling LOS across 2 hexsides at once. For instance, in your pic, CC2 and CC3, if a line went through the top hexside. I have an algorithm in my code to determine intersected hexes correctly, but not with the pixel data. I would have to do a fuzzy match, assuming I hit a hex outline, check the pixels above/below it. I'm not sure things are that exact, but I will look to see. VASL must handle it correctly, I could always look at their code for clues too.Likewise, if you've calculated the Bresenham offsets for the red LOS, you don't need to do it again for the blue LOS's, because they'll be the same.
Similarly, if you've calcuated e.g. the number of grain hexes between hexes A and B below, you can re-use that value when counting the number between A and C:
A - - - B - - - C
The > 30 LOS is a good idea, I'll keep that one in my back pocket, thank you! Yeah if I did this in C I'd definitely use pthreads. My AI is theaded and there are some increases there (there are also some bottlenecks specifically around data structure locking ,etc which prevent it from being a HUGE improvement).So, there are some low-hanging fruit that will give you a massive speed-up.
You might also impose a limit on LOS length e.g. 25 or 30 hexes. Unless it's DTO, LOS's are unlikely to be longer than that, and it might be acceptable to say that the AI doesn't consider anything farther than that.
This is also the kind of work that can be distributed. Python's threading support for CPU-heavy tasks is non-existent, so it would have to be multi-process, but everyone's got multi-core CPU's, so that would cut run times by several times. If you architect it right, you could even distribute the work over multiple hosts, if you have a spare computer, or send the tasks up to AWS
Yah, there's no chance of that I wrote a wrapper Java program that loads the VASSAL JAR, and then just calls the functions directly in that.
It's usually better to try improve the algorithm first, since the result might be Good Enough(TM), but even if you end up porting to C anyway, you're porting the improved algorithm, so it'll be that much faster again.If I end up porting to C (which is starting to seem likely) this may not be too much of a concern. I have a feeling it is going to be WAY faster.
combos = itertools.combinations( hexes, 2 )
for comb in combos:
check LOS beween comb[0] and comb[1]
I didn't say anything earlier because I didn't want to make you cry, but the rule for blocked LOS is that the obstacle has to visible on both sides of the thread i.e. it's not enough that the LOS goes through an obstructing pixel, the obstruction also has to be there on opposite, adjacent pixels. Sigh...The grain hex determination suffers from the same logic the intersected hexes did, it doesn't handle straddling LOS across 2 hexsides at once. For instance, in your pic, CC2 and CC3, if a line went through the top hexside. I have an algorithm in my code to determine intersected hexes correctly, but not with the pixel data. I would have to do a fuzzy match, assuming I hit a hex outline, check the pixels above/below it. I'm not sure things are that exact, but I will look to see. VASL must handle it correctly, I could always look at their code for clues too.
Totally agree. Any optimizations here would carry over nicely. Possibly allowing me to do multi-board easily.It's usually better to try improve the algorithm first, since the result might be Good Enough(TM), but even if you end up porting to C anyway, you're porting the improved algorithm, so it'll be that much faster again.
Wow, this is some good stuff. I'm not sure I totally grok the math of it yet, unless the idea is just to have a static table where if LOS from X to Y is blocked, others in a list are marked as blocked. As for determining the hexpairs in order of shortest range between them, I think that may be relatively easy with the current code.I think there are several simple optimizations you can do that will give a massive improvement in run times. The ideas below all revolve around either:
Identifying LOS's that don't need to be checked
- identifying work that doesn't need to be done
- not re-doing the same work
The code currently does something like this:
IOW, it checks the LOS between every hex pair combination on the map, all 59,685 of them Thing is, as you work your way through them, you can eliminate the need to check some of them.Code:combos = itertools.combinations( hexes, 2 ) for comb in combos: check LOS beween comb[0] and comb[1]
Imagine the code has determined that the LOS is blocked between O6 and R5:
View attachment 22354
It's obvious that if you extend the LOS at both ends, it will also be blocked between points farther out (i.e. left of O6 and right of R5), but because LOS is taken from the center of a hex, you can't just go to the next hex out and say that it's blocked as well (e.g. O6 and S5), because the LOS doesn't align with the original LOS (in this case, it is blocked, but it's not guaranteed).
However, if you consider LOS's that have a range that are integral multiples of the original LOS, you can guarantee that the LOS is blocked, because the LOS's do align with the original LOS:
View attachment 22361
Because the triangles are similar (aka "the geometry of ASL"), once you know that O6-R5 is blocked, you can quickly and cheaply determine that the following LOS's are also blocked, and don't need to be checked:
So, that's 8 LOS's that don't need to be checked, just on this board fragment - it'll be much more on a full board. And that's from a single blocked LOS. Every time you detect a blocked LOS, that lets you skip a bunch of other LOS's that don't need to be checked.
- O6-U5 ; O6-X4
- L6-R5 ; L6-U5 ; L6-X4
- I7-R5 ; I7-U5 ; I7-X4
I think the key is to check hex pairs in order of increasing range. That lets you detect short blocked LOS's earlier, which maximizes the number of longer LOS's you can eliminate in this way.
Good idea about re-using the counts, I hadn't thought of that. I think the big issue w/ Bresenham calls in my script isn't the LOS line call, but the per pixel call I'm doing to find which hex the current x,y is in. That seems crazy expensive, but it was the only way I could determine what hex it was in.Re-using Bresenham offsets
If the LOS between O6 and R5 is clear, there are still optimizations that can be done. Because the LOS's align, you can re-use the Bresenham offsets calculated for O6-R5 when checking pixels for R5-U5, L6-O6, etc.
View attachment 22360
This also means that you can re-use the counts for grain and brush in the O6-R5 segment when doing the O6-U5, O6-X4, etc. segments.
And this would be a good time to do the LOS checks as indicated below, since it's easy to get the Bresenham offsets by inverting and/or swapping the X/Y co-ordinates for the O6-R5 ones:
View attachment 22362
I don't how much time is spent calculating the Bresenham points, but while it's usually considered a fast algorithm, there's no better way to speed up an operation than by not doing it in the first place
It seems like there are a lot of re-use cases here which I should work on. I do a lot of caching like you mentioned in my C program (los, intersected hexes, covered arc hexes, etc) and it does use up more memory, but with C it seems manageable.Pre-computing the Bresenham points
The code is constantly calculating Bresenham points to determine which pixels to check for a LOS between 2 given hexes, but this is often unnecessary (e.g. because the offsets for O6-U5 are the same as, or can be derived from, the offsets for O6-R5), but also, they are independent of the board being analyzed, and so can be pre-computed and re-used for every board. Actually, they're even independent of the position on the same board i.e. if you've done it for O6-R5, not only do you not need to do it for R5-U5, you also don't need to do it for O7-R6, P6-S6, etc.
You could pre-compute the offsets for all 59,685 hex pairs, but I strongly suspect that won't be necessary, and you could probably get away with only doing them for one set of hex pairs up to a range of, say 5 to 10, because:
Pre-computing offsets for all the hex pairs would certainly be faster, but dramatically increases the amount of memory needed, and whatever performance gains you might earn by being clever in the code will be obliterated if your program starts swapping You could dynamically read them from disk, but disk access will be slow as well. However, if you do LOS checks in order of range, you could load/calculate just the offsets for the range you're currently checking - that could work.
- the offsets are independent of the starting hex
- the offsets repeat e.g. the offsets for a LOS of range 3 will repeat for every subsequent 3 hexes
- the need to check many of the longer LOS's will be eliminated by the first idea presented above
They key thing here is that you're doing an expensive operation inside a loop (so we want to move it outside the loop), and a lot of the time, it's calculating the same thing over and over again (either exactly the same thing, or something that could be derived from a previous calculation). You should be able to drastically reduce the number of times Bresenham points are calculated in the main loop, which will probably reduce the run time from hours to minutes. Convert that to C, and it might become seconds Add in a max. range for LOS's, and it will become even faster.
Haha, this should be fun to do!I didn't say anything earlier because I didn't want to make you cry, but the rule for blocked LOS is that the obstacle has to visible on both sides of the thread i.e. it's not enough that the LOS goes through an obstructing pixel, the obstruction also has to be there on opposite, adjacent pixels. Sigh...