Buying enough maps crashes the game

[chadwhitacre]

Steps

1. Never have the scout show up for a loooooooong time.
2. Consequently, store up lots of fur and scales.
3. Have scout show up.
4. Learn scouting (finally!).
5. Buy map.
6. Repeat (5) ad infinitum.

Expected

Be told when there are no more maps to buy.

Actual

Browser tab hangs. It feels like maybe there is an infinite loop looking for more world to uncover? There are in fact a few tiny little pockets of uncovered world remaining.

Screenshot after Reload

Environment

Chrome 54.0.2840.98 on macOS 10.10.5

[chadwhitacre]

Of course my first destination was the swamp. Would you believe it was in the very last part of the world I explored?

[chadwhitacre]

With relatively few blast sites, and no alien alloy in any of the battlefields, I ended up with only 13 alloy. Usually I find at least 16, which is enough that if you put it all in hull you don't even have to steer. Not this time! If I don't want to scour the suburbs for alloy (or save up enough fur to buy more alloy—we did that once, too! :), then I may have to actually fly the ship for once. :)

[chadwhitacre]

First attempt failed.

[chadwhitacre]

Second time was the charm. Exosphere with 4/13 hull. Truly a unique playthrough!

[Continuities]

It feels like maybe there is an infinite loop looking for more world to uncover?

Hah! Yup, I'll bet that's exactly how I wrote that. I should rewrite it in a less crappy way.

[farraj12]

farajlol

[ddugovic]

@Continuities Maybe make the world a torus (wrapping horizontally & vertically) to avoid overflow/underflow, and when an actor approaches an edge resize the map?

[Continuities]

Traversal isn't the issue. My original algorithm for finding unexplored areas of the world to uncover when purchasing maps is naive and lazy.

…

On Mon, Dec 26, 2016 at 10:24 PM Daniel Dugovic ***@***.***> wrote: @Continuities <https://github.com/Continuities> Maybe make the world a torus (wrapping horizontally & vertically) to avoid overflow/underflow, and when an actor approaches an edge resize the map? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#515 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEqIA-dPVZAOePlcCMsKwcZtjLPDroQmks5rMIT4gaJpZM4LBP2O> .

[pstauchCO]

@Continuities I've been trying to improve your algorithm for finding unexplored areas a bit, but I'm afraid I've run out of time (I'll keep going on it, but I need to get something in for a class I'm in). It presents a good opportunity to get your thoughts on what I'm doing, anyway.
Instead of searching for a random (x,y) coordinate pair that has not yet been uncovered, instead start at a randomly picked (x,y) pair and perform a spiral search (BFS) around the randomly selected vertex, testing each vertex as we go. Once a dark spot is encountered, we return the dark spot to the applyMap function and pass it to uncoverMap.
I haven't added bounds checking yet to make sure we only check vertices that are actually on the map, but it should still be sufficiently random.

// world.js

findDarkSpot: function(mask) {
  var x,y,queue = [],visited = [],darkxy = [];
  x = Math.floor(Math.random() * (World.RADIUS * 2 + 1));
  y = Math.floor(Math.random() * (World.RADIUS * 2 + 1));
  queue[0] = [x,y];
  while(queue.length > 0)
  {
    var u = queue.shift();
    if(!mask[x][y]) {
      // Found a dark spot
      darkxy = [x,y];
      return darkxy;
    }
    // Add vertices surrounding (x,y) to the queue if they have not yet been
    // visited.
    for(var i = x-1; i <= x+1; i++) {
      for(var j = y-1; j <= y+1; j++) {
        // Check if the vertex has already been visited
        var processed = false;
        for(var k = 0; k < visited.length; k++) {
            if(visited[k][0] == i && visited[k][1] == j) {
              processed = true;
            }
        }
        if (!processed) {
          // Check if the vertex has already been added to the queue
          // before pushing it on the queue (again)
          var discovered = false;
          for(var l = 0; l < queue.length; l++) {
            if(queue[l][0] == i && queue[l][1] == j) {
              discovered = true;
            }
            if(!discovered) {
              queue.push([i,j]);
            }
          }
        }
      }
    }
    // [x,y] has been processed. Time to move on.
    visited.push([x,y]);
  }
},

applyMap: function() {
  if(!World.seenAll){
    var x,y,mask = $SM.get('game.world.mask');
    var xy = World.findDarkSpot(mask);
    x = xy[0];
    y = xy[1]; 
    World.uncoverMap(x, y, 5, mask);
  }
  World.testMap();
},

[keybounce]

This bug seems to still be present. I think I just bought-out the whole world, or at least enough to make firefox spin cursor for a while, and then say "unresponsive script".

Worse, after "stop script", neither "say goodbye" nor "save" have any effect. Lets hope a cmd-R reload works. ... Yes.

... Ok, how do you copy the map?

[SengulolanCem]

Can you please provide a saved game for this issue ?

[Roarez]

I found the source of the problem after a few tests. The problem is not with buying maps but with how dark spots where bieng searched for. In particular within the applyMap function.
applyMap: function() {
if(!World.seenAll){
var x,y,mask = $SM.get('game.world.mask');
do {
x = Math.floor(Math.random() * (World.RADIUS * 2) + 1);
y = Math.floor(Math.random() * (World.RADIUS * 2) + 1);
} while (mask[x][y]);
World.uncoverMap(x, y, 5, mask);
}
World.testMap();
},
where either for x or y, Math.floor(Math.random() * (World.RADIUS * 2) + 1), will cover values from 1 to 60, missing 0. Bieng that the map array is a 61x61, if any of the last few dark spots are at the very top or left of the map (x= 0 or y= 0) the do while will enter an infinite loop and thus the crash.
the easy way to fix is simply moving the +1 further inside the brackets, like so: Math.floor(Math.random() * (World.RADIUS * 2 + 1))
I made a PR that does just that, already tested it too.
#626
You can also test it easily by opening the browser console and typing World.applyMap() a quite a few times after generating a map ofcourse. In the current case it should eventually crash due the reasons i stated above and World.seenAll always being false. If you try out the quick fix, World.seenAll should eventually be true . You can also trigger the Scout to appear with
Events.startEvent(Events.EventPool[n]) where n is the number of the Scout event (sometimes its 7 other times 8). this way you can also confirm that the buy map button gets disabled and you can also test fully uncovering the map from there. Sorry for the long post and i hope this helps

[Continuities]

Makes sense to me. Not an actual fix, as we can still eventually run out of dark spots and loop infinitely, but it'll delay the inevitable just a little longer.

Ultimately, something like @pstauchCO proposed is the right solution: Choose a random spot, then conduct an ever-expanding search from that spot until we either find a dark spot or run out of places to look. We should probably choose a spot (or determine that there are no more spots) before even showing the Scout dialog so that 'buy map' can be disabled if there are no more maps to buy.