LOSData File Format

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
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 :)
I have all this info already in a separate file for each board! This is an excellent idea. Although I feel like I'd still have to parse the line to determine which hexes are intersected. Although this could (and now I'm thinking should) be pre-calculated. It's always the same for a single mapboard!

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).
View attachment 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.
I haven't tackled hedge/bocage yet (are those terrain types even in SK?). I've added full concealment so I imagine my engine will slowly add parts of regular ASL. I definitely want to add Snipers to my AI engine.

The idea about using the list to skip hexes is good, ESPECIALLY for open ground as there are usually a lot of those.

I need to mull all of these ideas over. Some are very simple to implement, some will take a bit of work. :)
 

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
I'm not sure I totally grok the math of it yet
If you haven't read it already, check out the article "The Geometry Of ASL" (Banzai! 5.2), or search for the mathematical term "similar triangles". The angle of two LOS's must be the same if they are to align, and that will only happen if the triangles are similar.

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.
The idea is that you're working your way through a list of hex pairs, checking LOS's, and if you detect a blocked LOS, you can infer that other hex pairs must also blocked, and so don't need to be checked. So, you could maintain a separate table of hex pairs that you know to be blocked (and check it before you start processing the next hex pair), or you could just remove them from the list of hex pairs still to be checked.

As for determining the hexpairs in order of shortest range between them, I think that may be relatively easy with the current code.
Yep, but this is something that should be pre-computed, since it's independent of the board.

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.
Yes. Not only are you doing expensive Bresenham calculations inside a loop, but inside nested loops :) But a table mapping X,Y co-ordinates to hexes can be pre-computed, since it's independent of the board. Doing this alone will slash run times immensely.

And you don't need to use Bresenham's algorithm for this, since you're building a table for every pixel on the board. Using a bit of math, figure out what pixels belong to a single hex with centre (0, 0). Then do a bit more math to calculate the centre position of each hex on the board, and it's then easy to figure out the X,Y co-ordinates of every pixel in each hex.

You'll have to worry about some pixels being missed, or being counted twice, but that's easy to handle. Or, if you care about where hex edges are, figure them out, and that will help you decide what to do with pixels that could be in two hexes.

it does use up more memory, but with C it seems manageable.
Python is an absolute pig for memory. There are some data structures that are supposed to make things more efficient, but you really need to understand its internals if you want to make things better. Using numpy is probably the way to go.
 
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
I haven't tackled hedge/bocage yet (are those terrain types even in SK?).
It doesn't really matter what the terrain is. The key point is that there are some hex edges that block LOS, so if you can quickly identify hex pairs whose LOS crosses these hex edges, you don't need to check them.

I reckon VASL might have this information somewhere, since it's able to do things like convert walls to hedges. Otherwise, if it's difficult to do programatically, it might even be worth defining them manually. There won't be that many of them per board, and the savings to be gained probably make it worthwhile. And even if you don't do it for a given board, things will still work, just a bit more slowly.

Now that I think about it, if you track LOS-blocking hex-sides like this, there's no need to check for 100%-obstacle hexes, since by definition, all their hex-sides will be LOS-blocking.
 
Last edited:

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I'm doing some optimizations and also re-writing in C++. The parts that are done are crazy fast now. :)

In re-writing I think I found that I may be doing something fundamentally wrong. This is reading the image and then writing out the Java serialized data so there could be another level to it. The way I am reading the data was after the extents of the map, etc I walk the data and read in 2 bytes for each in a loop. First byte was terrain_type, second byte was elevation. I'm pretty sure I figured this out by going over the VASL code. After all that was read in, I then read a byte for stairway in the same way. Looking at my read in data, things don't look correct. I had spot checked a bunch of LOS on boards and they worked, but I don't think it is 100% correct the way I'm doing it. However, when walking the stairway bytes, I was seeing terrain codes. :(

In general the format of the map data after a few fields I don't use is:

map_width_in_hexes
map_height_in_hexes
map_width_in_pixels
map_height_in_pixels

terrain_code byte
elevation byte
...

Another thing that makes my head hurt is handling the shared pixels of the hex outlines. I'm trying to compensate for it, but it's not exact.
As mentioned previously, I also need to handle terrain on each side of the hex sides.

@DougRim could you possibly shed some light here? Am I missing something? I'm parsing the serialized Java data in C++ and that is working as far as endianness/bytes/ints etc.
 

Pacman Ghost

Senior Member
Joined
Feb 25, 2017
Messages
590
Reaction score
298
Location
A maze of twisty little passages, all alike
Country
llAustralia
Another thing that makes my head hurt is handling the shared pixels of the hex outlines. I'm trying to compensate for it, but it's not exact.
I suggested in another post that you figure out where the hex edges are first e.g. in the diagram below, if you figure out which pixels contain a hash, then everything else must be an interior pixel:
.... #......#......#
......######........#
.....#......#......#
#####........######
.....#......#......#
......######........#
.....#......#......#


This will use a lot of memory, but you could map co-ordinates to hexes in another way that will be a bit slower (although it probably won't be a problem if you do it in C), but uses no memory.

For a given pixel, it's trivial to figure out if it lies inside one of the orange boxes:
22454

If the pixel is not in one of these boxes, figure out which red box it's in, and then using similar triangles again :), you can figure out which red triangle it's in, and hence determine which hex the pixel is in.

The problem of pxiels partially covering a hex edge comes back, but if you use a lookup table for the points in one of the red triangles, that goes away.
 
Last edited:

Tuomo

Keeper of the Funk
Joined
Feb 10, 2003
Messages
4,652
Reaction score
5,537
Location
Rock Bottom
Country
llUnited States
This is reading the image and then writing out the Java serialized data so there could be another level to it. The way I am reading the data was after the extents of the map, etc I walk the data and read in 2 bytes for each in a loop. First byte was terrain_type, second byte was elevation. I'm pretty sure I figured this out by going over the VASL code. After all that was read in, I then read a byte for stairway in the same way. Looking at my read in data, things don't look correct.
It sounds like you're doing it right. Remember the Java serialized data adds something (I think it's a 5 byte thing) every 1024 bytes, just to let you know there's another 1024 coming. The last such spacer is tells you how many bytes are left in the file (some number less than 1024).
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I suggested in another post that you figure out where the hex edges are first e.g. in the diagram below, if you figure out which pixels contain a hash, then everything else must be an interior pixel:
.... #......#......#
......######........#
.....#......#......#
#####........######
.....#......#......#
......######........#
.....#......#......#


This will use a lot of memory, but you could map co-ordinates to hexes in another way that will be a bit slower (although it probably won't be a problem if you do it in C), but uses no memory.

For a given pixel, it's trivial to figure out if it lies inside one of the orange boxes:
View attachment 22454

If the pixel is not in one of these boxes, figure out which red box it's in, and then using similar triangles again :), you can figure out which red triangle it's in, and hence determine which hex the pixel is in.

The problem of pxiels partially covering a hex edge comes back, but if you use a lookup table for the points in one of the red triangles, that goes away.
Once I have this ported I'm going to go over all of your suggestions, there's a lot to mine in there for optimizations. Thanks for all of it!
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
It sounds like you're doing it right. Remember the Java serialized data adds something (I think it's a 5 byte thing) every 1024 bytes, just to let you know there's another 1024 coming. The last such spacer is tells you how many bytes are left in the file (some number less than 1024).
This was helpful thanks! My python code I was doing that correctly, I forgot to bring over to my C program the byte counting and grabbing the length once it had gone to 0. And yeah, it seems to be 5 bytes 0x7a and then 4 bytes of size.
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
Interesting data point on the VASL pixel maps for geomorphic boards. I assumed there was equal spacing between the centers of hexes in both horiz/vert. It doesn't seem to be the case.

Assuming 56 pixels in the horizontal and 64 in the vertical between LOS centers (measured in a drawing program):

In the horizontal there is a missing pixel every 5 columns, there is also one missing pixel at the end (the GG column ends up one off).
In the vertical there is a pixel missing every 2 rows - for even columns starting at row 2, and for odd columns starting at row 3.

I had been doing slight modifications based on x and y to get the centers right and recognized there was somewhat of a pattern going on.

This was on bd05, not sure if is the case with all boards. It also could be the case this is just how hexmaps are, not completely symmetrical! :)
 

BigAl737

Elder Member
Joined
Apr 5, 2011
Messages
1,507
Reaction score
1,269
Location
AK
Country
llUnited States
VASL hexes aren’t square. Besides being a catchy catch phrase, it’s true. The Y axis is compressed.
 

Gordon

Forum Guru
Joined
Apr 6, 2017
Messages
2,488
Reaction score
2,940
Country
llUnited States
VASL hexes aren’t square. Besides being a catchy catch phrase, it’s true. The Y axis is compressed.
Isn't it the other way around? Physical geoboard hexes are "compressed", VASL hexes are true hexagons.
 

BigAl737

Elder Member
Joined
Apr 5, 2011
Messages
1,507
Reaction score
1,269
Location
AK
Country
llUnited States
Geoboards are actually taller than uniform.

A VASL geoboard hexgrid is 1800x645 px.
A uniform hexgrid generated in Inkscape is 1800x651 px.
A physcial geoboard hexgrid (at least to the best of my measurements) is 1800x660 px.

So you must compress the height of a uniform and geoboard hexgrid by 6 and 15 pixels respectively to make it fit the VASL hexgrid.
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
Geoboards are actually taller than uniform.

A VASL geoboard hexgrid is 1800x645 px.
A uniform hexgrid generated in Inkscape is 1800x651 px.
A physcial geoboard hexgrid (at least to the best of my measurements) is 1800x660 px.

So you must compress the height of a uniform and geoboard hexgrid by 6 and 15 pixels respectively to make it fit the VASL hexgrid.
This explains a lot. 1800 / 32 (the 32 being how many hexes there are horizontally, 31 + 2 halves) == 56.25. That explains the "loss" of 1 pixel every 5 hexes.

The vertical 64.5 per hex for vertical spacing explains needing to add a pixel every 2 hexes vertically.

What is causing me issues is that I'm doing everything as integers (since I can't find the pixel at an x coordinate of 56.25, etc).

It's close enough for me! :) My small changes in processing have all of the centers where they are in the VASL board image.
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
C++ version is done and much faster. bd01 took 54 minutes. With some of the optimizations suggested in this thread I'm sure I can cut it down a lot more leaving headroom for multi board maps.
 

ScottKittyHawk

Recruit
Joined
Nov 12, 2021
Messages
19
Reaction score
11
Country
llUnited States
I had to take a break from my project and it looks like some other interesting things have happened! I recently completed a project for a DARPA challenge and there was some knowledge that could be transferred to this project. I've dusted off my code and made a number of improvements. In order to address some unresolved hurdles, the current version ignores inherent terrain and elevation. A picture of the result is below:
23452
The left image is the actual VASL map, the center image is the actual LOS data, and the right is the output of the neural network having be fed only the map. It matches the training image pretty well so this is good progress. A larger image with more samples is attached. The next steps include: Adding color noise to the map boards (to better accommodate maps not conforming to the VASL specification), addressing elevation, and addressing inherent terrain.
23453
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
Amazing stuff, could you talk a little about the process, what software you are using, etc? Very curious...
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I spent some time with my app and managed to cut down the time by a good margin, and it's more accurate! There are rare occasions (when the blocking terrain is right near the edge of a hex) where I was incorrectly determining there wasn't LOS when there is. The speedup is due to a change I made which took a while to understand, and I'm pretty sure it was suggested in a previous post, but I didn't try implementing it, but now that I'm doing lots of maps, the slow speed is a killer.

The change was to convert from axial coords to cube and then calculate the distance w/ the cube coords rather than using Bresenham to get the line of pixels and taking the length of that for distance. It's a LOT faster now!

The hardest part was getting the x and y "slop" accounted for (as mentioned in an earlier post)
 

telengard

Member
Joined
Jan 6, 2009
Messages
31
Reaction score
10
Location
New Hampshire
Country
llUnited States
I've updated the app to support multi board maps and also rotation. Only thing left is offset maps, like S25. Can rip through a 2 board map in 10 minutes!
 
Top