forums.cubicle7.co.uk
archive

Glorelendil wrote:Update: I'm rewriting the whole thing. Well, lots of copying and pasting, but better to start with a clean slate than try to fix the current mess.

Happy to know the Journeyometer is alive! Great, great tool.
Thanks Glor.

Glorelendil wrote:For any computer scientists out there, I'm going to need an algorithm that, given a contiguous and closed sequence of coordinates in a hex-shaped grid, determines if a cell represented by a pair of coordinates is inside enclosed by the sequence. (In other words, if regions are defined by their borders, test whether a hex cell is inside that region.) It should be as zippy as possible, so that I can iterate through all regions querying which one(s) the cell is in.

Alternatively, given the border, generate the list of all additional cells that are enclosed within that border.

Let's see:

function InThisRegion (coords, region) {
#do the simple tests first
if ($hash_region_looked_up{"region.name-coords.x-coords.y"}) { return $hash_region_looked_up{"region.name-coords.x-coords.y"}
#okay the above is a bit tricky. Essentially, we never want to do the same math more than once. So once we figure out if a coord is in a certain region, we create a dictionary entry and then get the result from that. If your language doesn't support this, then maybe it could be some sort of math that would create a unique number that you could look up in an array. Or just switch to a language that has hashes.

if (coords.y < region.minimum_y) { $hash_region_looked_up{"region.name-coords.x-coords.y"} = false; return false; } #I'm assuming that these values are computed when a region is defined, and associated with the data structure
if (coords.y > region.maximum_y { $hash_region_looked_up{"region.name-coords.x-coords.y"} = false; return false; }
if (coords.x < region.minimum_x) { $hash_region_looked_up{"region.name-coords.x-coords.y"} = false; return false; }
if (coords.x > region.maximum_x) { $hash_region_looked_up{"region.name-coords.x-coords.y"} = false; return false;}

#we might have an actual hit

#before I go any further, I need to know how you're defining the path. Is it a series of global coordinates in an ordered list? Or something more esoteric?

}

I'm doing a bad job explaining. I don't want to have to record every single cell inside a region because it's a metric shitload of work. Instead I want to just transcribe the borders and then let the silicon fill in the middle by generating all the interior coordinates. When that is done then I can do something like zed and aramis are proposing.

(Off topic funny story: when I was 14ish I raced Lasers, a kind of sailboat. I wanted to name it Earrame, and mentioned it to my mom. She surprised me by buying the adhesive letters: A R A M I S. I think of that every time I see your posts.)

By the way, cool idea last night:
1) encode regions by global coords, not local.
2) each of the four maps has an offset coordinate. E.g Eriador is 0,0 and Rohan might be 127, 167 or something
3) now if you start drawing a route and hit the edge, you can switch to the new map and your route will appear. Any segments you can't see will still be there.

The result should be that you, for example, trace Frodo's route from bag end to mordor.

Global coordinates sounds very cool. As for your region problem, as for your region problem I have an idea, but it will require diagrams and swee I have an idea, but it will require diagrams and pseudocode. Later, in other words.

One question is 0,0 upper left or lower left?

Upper left just to avoid an additional transformation.

Okay so here's a really terrible diagram, done on my son's Chromebook:



So when the outline is drawn out, the extents should be recorded, something like:

Region.Minimum_X = 151;
Region.Width_X = 5;
Region.Minimum_Y = 69;
Region.Height_Y = 4;

then after we draw the outline, we need to figure out the inside area. Let's assume that we can associate an array with the data structure. We also can use local coordinates (since our offset is handily provided by the minimums above) and we don't need to record maximums either (since the width and height above will work nicely).

We also assume that we wrote the outline that the user defined into the array because that makes sense. We'll use booleans. As the user draws, the width and height are extended as needed. If a fixed array is needed, then you just need to figure out the biggest possible region.

So we do this:

int v = 0;
int h = 0;
boolean in_Region = FALSE;

if (v < region.height) {
if (h < region.width) {
if ((in_Region == TRUE) && (region.array[h.v] == TRUE)) {break;} #if in_Region is already set and we hit an array point that registers as TRUE we must have hit the other edge of the user defined border
if (region.array[h,v] == TRUE) {in_Region = TRUE;}
if (in_Region == TRUE) { region.array[h,v] = TRUE; }
h++;
}
in_Region = FALSE;
h = 0;
v++;
}

Of course, as previously mentioned, we can then use a hash to use global coordinates to figure out if we're in a particular region.

Does that make sense?

Yes, it does, but while driving today I came up with a solution. I'll create the equivalent of a "paint bucket" (that is "fill") tool:

1) Click on a cell inside a border
2) Add that cell to a set (call that "function hexCrawl")
3) Recursively check all six neighbors: if the neighbor is not assigned to a region, call function hexCrawl with that cell as the argument
4) If a neighbor *is* assigned to a region, assign all cells in the set, currently and in the future, to that region.

Task list:
1) Get global coordinates working
2) Rebuild cell-selection tool to be easier and more intuitive than what it has been (rules: single click or click & drag will both toggle cells, based on the inverse of the starting location. Have a clear button, and keyboard shortcut, to erase all selected cells, instead of deleting current selection when you click on a blank cell.)
3) Use new tool selection cell to define region borders
4) Build paint bucket tool and use that to fill in regions
5) Profit!

Progress Update:

1) All four maps from Maps & Journeys integrated.

2) Global coordinates are working. You can select cells that run to the edge of the map, and when you switch to the adjacent map (e.g., going over the High Pass into Wilderland) the selected cells are still selected. You can hop all over the four maps without losing your selections.

3) I've started tagging the regions for the new database (JSON flat file, not SQL). That's going to be a big, un-fun job.

4) I'm allowing cells that straddle a border to be tagged for multiple regions. The algorithm for computing journeys will show some smarts about choosing which region such a cell belongs to.

EDIT:

5) Journeys now being computed. But I commented out the code that includes locations, so a journey that passes through Beorn's House (for example) won't break that region up into two legs. I can add this back in once everything else is working.

Ha! I WTFPWN'd that code. It's now solving for ambiguous routes. It picks the longest route it can find that includes all the selected cells, potentially ignoring hexes that cannot be gone through without backtracking (I still need to flag those hexes as extraneous).

This means that you can make a 120 degree turn in your route and it doesn't get confused or skip the "elbow" of the turn. If you want to skip the elbow you can just deselect it.

In the live version this is considered "ambiguous" and you won't get a valid journey.

E.g.:


For those interested in the geekiness, I'm finding the route recursively rather than iteratively. It searches all valid routes and returns the longest one.