LOSData File Format

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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.
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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.
 

DougRim

Forum Guru
Joined
Apr 23, 2012
Messages
1,957
Reaction score
2,234
Location
Ottawa
Country
llCanada
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.
You are right, I was confusing it with another python program that he had posted there. My mistake.
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I ended up implementing this myself and it is working great so far, it's a little slow as I do it in python (takes about 30 seconds to determine the LOS from every hex to each other hexe).

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.

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.

I 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).

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.
 

DougRim

Forum Guru
Joined
Apr 23, 2012
Messages
1,957
Reaction score
2,234
Location
Ottawa
Country
llCanada
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.
 

DougRim

Forum Guru
Joined
Apr 23, 2012
Messages
1,957
Reaction score
2,234
Location
Ottawa
Country
llCanada
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.
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().
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.
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 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).
Terraintypes are defined in the SharedBoardMetadata.xml file which is located in the dist/boardData directory. See lines 1100 and following
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.
Let me know which parts above are not clear and I will elaborate further.

Doug
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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
Thank you Doug, super helpful! Especially the terrainTypes. I was looking all over the code, so in the totally wrong place!
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I updated this script not too long ago, so I'm posting it here. The changes are:

  • Way simpler logic for handling LOS
  • Determines all intersected hexes between src and target
  • Supports determining LOS intersected grain hexes
  • Supports determining LOS intersected brush hexes
  • Removed some functions that were (now) only called once and inlined them, speeds things up
I should also mention, this script does much more now than the previous one, and it takes a LONG time to run (on board y it takes over 15 hours).
The bulk of the time is spent calling the bresenham function to get points on a line. This is done for every pixel to see
if the point is within the extents of a hexagon. I may port this code to C for the speed increase.

Interesting data point. The number of unique hex to hex combos on a std mapboard is 59,685. :)

My ASL computer AI program is coming along great! I have almost all rules from SK1 implemented and a few things from SK2 as well as some additional stuff like concealment. Really enjoying playing it, I also have FOW which is something that regular concealment can't do. It's sorta like HIP for all units if they are concealed. I never know where the enemy is until it does something to unconceal itself.

--- I didn't mean to remove the previous post, I thought the delete (which was right under the attachment) would just delete the attachment, whoops
 

Attachments

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
it takes a LONG time to run (on board y it takes over 15 hours).
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.

This pre-calculation can also be sped up by taking advantage of the fact that there are a lot of symmetries e.g. LOS going in direction 1 are the same as going in direction 4, but Y is inverted. You probably only need to calculate LOS's in a 45-degree arc, then get the rest by inverting X and/or Y values, which cuts the workload by 7/8.

My ASL computer AI program is coming along great!
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... :rolleyes:
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
Definitely some optimizations. This python script generates output that I load into my 'C' program so everything is cached as to not affect performance. It's just this one time pass to generate the data that is such a long hit. 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. Elevation is another thing I need to figure out how to handle.

Once I feel like what I have is stable, I will ask MMP if I can release it. It is a console based program and pretty much requires the ownership of the physical game to play so I'm hoping they would be OK with it. It looks intimidating, but I don't find it bad at all, especially as it gives me a decent opponent!

Here's a screen grab of both sides being AI at a very low depth (so pretty much awful play):
 

Attachments

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
It's just this one time pass to generate the data that is such a long hit.
15 hours has got to hurt, every time you make a change. I started on mainframe batch systems, so I know the feeling... :rolleyes:

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.
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.

Here's a screen grab of both sides
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... :)
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
15 hours has got to hurt, every time you make a change. I started on mainframe batch systems, so I know the feeling... :rolleyes:
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.

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.
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 y

A1:Y1:1:B0,C1,D0,E1,F0,G1,H0,I1,J0,K1,L0,M1,N0,O1,P0,Q1,R0,S1,T0,U1,V0,W1,X0:S1,U1:

There's LOS (the 1) and it goes through all of those hexes, and also the 2 grain hexes S1, and U1. Hehe, in looking at this I already see an issue. This particular LOS crosses 2 hexes along the same side every other hex. I handle this when I algorithmically determine intersected hexes, but this method (using the pixel data) seems to be off a bit. Looks like I have a little more work to do. :)

The fields are separated by ':'. It goes src hex, targ hex, LOS, intersected hex list, grain hex list, brush hex list.
I then load this into my program and it is all cached so there's virtually no overhead for checking LOS/hinderances other than maybe walking a short list.

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.

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... :)
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).

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. My "engine" is very straightforward externally and can easily have a console, web, or std UI. The engine produces all possible actions (in which there can be MANY) and the input is a choice by either the human player or by the AI player, and it just does that over and over until the game ending conditions are met.

All of the data is stored in xml (units, scenario logic, mapboards, etc).
The AI is no whiz, but it plays a decent game to me at least, I'm surprised by it a lot, especially at higher depths.
 

Attachments

Last edited:

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
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.
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.

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.
22344

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

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 :)

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.
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.
 
Last edited:

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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.
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.

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
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.

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 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.

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.
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).

thanks for all of your thoughts, I appreciate it!!
 

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
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.
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.

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 work that doesn't need to be done
  • not re-doing the same work
Identifying LOS's that don't need to be checked

The code currently does something like this:
Code:
    combos = itertools.combinations( hexes, 2 )
    for comb in combos:
        check LOS beween comb[0] and comb[1]
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.

Imagine the code has determined that the LOS is blocked between O6 and R5:
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:
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:
  • O6-U5 ; O6-X4
  • L6-R5 ; L6-U5 ; L6-X4
  • I7-R5 ; I7-U5 ; I7-X4
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.

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.

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.
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:
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 :)

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:
  • 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
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.

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.

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.
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...
 
Last edited:

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
And here's another optimization that could give big savings, depending on what's on the board.

Build an index such that for any hex on the board, you can quickly get a list of every hex pair whose LOS goes through that hex. It will take some time to build, but since it's independent of the board being analyzed, you only have to do it once.

Identify hexes on the board that are 100% obstacle e.g. interior building and woods hexes (maybe VASL has this information already?), and using the index created above, you now have a list of hex pairs where it's impossible for there to be a clear LOS. Imagine what that could do for board 52 :)

You could even extend this idea to be able to look up hex pairs whose LOS goes through a given hex-side - this lets you quickly discard any hex pairs that have a LOS that cross a wall or hedge or bocage (assuming non-adjacency).

This could also include interior building/woods hexsides e.g. in the diagram below, a LOS that crosses the interior U2-U3 hexside cannot possibly be clear (assuming non-adjacency).
22370
But you would need to be able to identify such interior hexsides quickly.

You might also be able to do a similar trick for hexes that are 100% non-obstacle (e.g. open ground, maybe with a bit of road) - if the LOS enters such a hex, you don't need to check all the LOS pixels in that hex, you can just skip to where the LOS leaves the hex, and continue checking from there.
 
Last edited:

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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.
Totally agree. Any optimizations here would carry over nicely. Possibly allowing me to do multi-board easily. :)

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 work that doesn't need to be done
  • not re-doing the same work
Identifying LOS's that don't need to be checked

The code currently does something like this:
Code:
    combos = itertools.combinations( hexes, 2 )
    for comb in combos:
        check LOS beween comb[0] and comb[1]
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.

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:
  • O6-U5 ; O6-X4
  • L6-R5 ; L6-U5 ; L6-X4
  • I7-R5 ; I7-U5 ; I7-X4
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.

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.
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.

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 :)
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.

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:
  • 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
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.

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.
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.

I feel like if I could change the "what hex am I in" code to not do a Bresenham call ever point of the line it would make a HUGE difference.

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...
Haha, this should be fun to do! ;)

thanks again for all this info, it's awesome!
 
Top