Off by one error in map generator

[mrvn]

Start the game in sandbox and teleport to the edge of the world:

/c game.player.teleport({-1048550, 0});

Now run left for a bit and the game crashes.

/c game.player.teleport({-1048576, 0});

Instant crash.

/c game.player.teleport({-1200000, 0});

Game refuses to teleport out of the map.

Looks like there is an off-by-one error in the check what is inside the map.

Code: Select all

Factorio crashed. Generating symbolized stacktrace, please wait ...
  87.904 Warning Logger.cpp:483: Symbols.size() == 21, usedSize == 12
#0  0x0000000000847d98 in Logging::flush() at /tmp/factorio-build-wMleZS/src/Util/Logging.cpp:62
#1  0x000000000084bc95 in Logging::logAndAbortOrThrow(char const*, unsigned int, LogLevel, std::string const&) at /tmp/factorio-build-wMleZS/src/Util/Logging.cpp:87
#2  0x0000000000915e79 in Chunk::Chunk(Surface&, ChunkPosition const&) at /tmp/factorio-build-wMleZS/src/Surface/Chunk.cpp:692 (discriminator 3)
#3  0x0000000000c56b38 in Surface::getChunk(ChunkPosition const&) at /tmp/factorio-build-wMleZS/src/Surface/Surface.cpp:192
#4  0x0000000000c57042 in MapGenerationManager::request(Surface&, ChunkPosition const&, ChunkGeneratedStatus::Enum) at /tmp/factorio-build-wMleZS/src/Map/MapGenerationManager.cpp:110
#5  0x0000000000c574ac in Surface::requestToGenerateAndActivateChunk(ChunkPosition const&) at /tmp/factorio-build-wMleZS/src/Surface/Surface.cpp:973
#6  0x0000000000c69f79 in Surface::requestToGenerateAndActivateChunks(ChunkPosition const&, int) at /tmp/factorio-build-wMleZS/src/Surface/Surface.cpp:966
#7  0x0000000000c6f130 in Player::generateAndActivateNeighborChunks() at /tmp/factorio-build-wMleZS/src/Player.cpp:779
#8  0x000000000095e535 in Player::generateFarAwayChunks() at /tmp/factorio-build-wMleZS/src/Player.cpp:784
#9  0x000000000151650f in Player::update() at /tmp/factorio-build-wMleZS/src/Player.cpp:398
#10 0x0000000000007494 in Map::update() at /tmp/factorio-build-wMleZS/src/Map/Map.cpp:1314
#11 (nil) in Game::update() at /tmp/factorio-build-wMleZS/src/Game.cpp:163
Stack trace logging done
  87.904 Error Chunk.cpp:692: Trying to make chunk at unreasonable position [-32772, -4]
Logger::writeStacktrace skipped.
  87.904 Error CrashHandler.cpp:174: Map tick at moment of crash: 2079
  87.904 Error Util.cpp:67: Unexpected error occurred. If you're running the latest version of the game you can help us solve the problem by posting the contents of the log file on the Factorio forums.
Please also include the save file(s), any mods you may be using, and any steps you know of to reproduce the crash.

------------- Error -------------
Unexpected error occurred. If you're running the latest version of the game you can help us solve the problem by posting the contents of the log file on the Factorio forums.
Please also include the save file(s), any mods you may be using, and any steps you know of to reproduce the crash.

Log file location: /home/mrvn/factorio/factorio/factorio-current.log

Would you like to copy the path to the clipboard?
---------------------------------
  88.635 Info CrashHandler.cpp:615: Wrote minidump to /home/mrvn/factorio/factorio/factorio-dump-current.dmp
Aborted

[Rseding91]

What? I'm not seeing anything here that would be considered a bug.

If you tell the game to generate anything *more* than 1048576 tiles from 0,0 it aborts.

[Zavian]

I'm guessing he would prefer for the game to simply not generate tiles/chunks rather than abort.

[mrvn]

What? I'm not seeing anything here that would be considered a bug.

If you tell the game to generate anything *more* than 1048576 tiles from 0,0 it aborts.

Wrong, please actually read till the end of the bug report.

If you tell it to generate something noticably more than 1048576 tiles it correctly refuses to do so. Only when you tell it to generate just a hair more than 1048576 then it crashes. So there already is a check higher up for out-of-map, the check just allows some coordinates that the lower level already don't like. I assume it's off by one chunk. Something like

Code: Select all

if (x < -MAX_CHUNKS << 5)

instead of

Code: Select all

if (x <= -MAX_CHUNKS << 5)

.

[Rseding91]

What? I'm not seeing anything here that would be considered a bug.

If you tell the game to generate anything *more* than 1048576 tiles from 0,0 it aborts.

Wrong, please actually read till the end of the bug report.

If you tell it to generate something noticably more than 1048576 tiles it correctly refuses to do so. Only when you tell it to generate just a hair more than 1048576 then it crashes. So there already is a check higher up for out-of-map, the check just allows some coordinates that the lower level already don't like. I assume it's off by one chunk. Something like

Code: Select all

if (x < -MAX_CHUNKS << 5)

instead of

Code: Select all

if (x <= -MAX_CHUNKS << 5)

.

You're not understanding how generating chunks works. When you ask to teleport to < the limit it works fine because the game only generates the 1 chunk you land on to put you there. But then once there your player starts generating chunks around himself and he asks the game to generate one outside the limit and it crashes.

The lua-script teleport method checks if the destination is within the limits and blocks it if it's not. The game doesn't check anywhere else except on chunk creation to avoid the overhead of doing the check.

There is no off-by-one error just you not understanding what's happening.

[mrvn]

What? I'm not seeing anything here that would be considered a bug.

If you tell the game to generate anything *more* than 1048576 tiles from 0,0 it aborts.

Wrong, please actually read till the end of the bug report.

If you tell it to generate something noticably more than 1048576 tiles it correctly refuses to do so. Only when you tell it to generate just a hair more than 1048576 then it crashes. So there already is a check higher up for out-of-map, the check just allows some coordinates that the lower level already don't like. I assume it's off by one chunk. Something like

Code: Select all

if (x < -MAX_CHUNKS << 5)

instead of

Code: Select all

if (x <= -MAX_CHUNKS << 5)

.

You're not understanding how generating chunks works. When you ask to teleport to < the limit it works fine because the game only generates the 1 chunk you land on to put you there. But then once there your player starts generating chunks around himself and he asks the game to generate one outside the limit and it crashes.

The lua-script teleport method checks if the destination is within the limits and blocks it if it's not. The game doesn't check anywhere else except on chunk creation to avoid the overhead of doing the check.

There is no off-by-one error just you not understanding what's happening.

You are right, I don't know your code. But seriously? "overhead of doing the check"?

You already have a check in place. Just not a check against the right value. If you say the problem is extra chunks besides the one you land on then the right check is "if (x < 2^20 - MARGIN_BECAUSE_MORE_CHUNKS_GET_GENERATED)". That certainly has nothing to do with avoiding overhead. There is no cost increase there at all. That's not something that takes O(n^2) time or anything. It's one comparison for each direction. Now next you will say that the margin is variable so that isn't a constant anymore?

Map generation stops at 1000000 already. Everything past that point is void (which you can landfill by the way). So any teleport past that point doesn't make sense. Why allow it if you know there is only void there and that the chunk generator will crash the game. All this needs for the game not to crash on teleport is to lower your constant from 2^20 to 1000000 in the check. 48576 tiles should be a large enough margin for anything.


There is no excuse for a game crashing. Ever. It happens but don't excuse it, fix it.

[Zavian]

Well in my opinion the game still should not crash. By all means refuse to generate chunks outside the limit, but don't crash. (Don't forget that it is possible for players to disable the autosave, or set it to once an hour, so a crash could potentially mean that an hour or more of playtime building might be lost).

Just how expensive is the check, compared to the actual cost of generating chunks. Is the optimisation worth it?

Interestingly in testing this behaviour (after I wrote the above) I get different behaviour to that described by Mrvn. For me, attempting /c game.player.teleport({-1048550, 0}), causes a crash. Teleporting to -1048000,0 leaves be in a black space, which I imagine is outside the chunk generation boundaries. Teleporting to -1000000,0 leaves me right on the edge of that boundary, and the game won't let me walk left nor will it generate new chunks to the left. (0.16.51 Steam version, totally vanilla on Windows 10. Log below. I have no idea what the "time travel logging" is about).

Maybe an appropriate fix is for the teleport api to enforce the 1,000,000 tile limit that the chunk generator seems to obey.

Code: Select all

   0.001 2018-07-03 22:20:12; Factorio 0.16.51 (build 36654, win64, steam)
   0.001 Operating system: Windows 10 (version 1803) 
   0.002 Program arguments: "D:\Steam\steamapps\common\Factorio\bin\x64\Factorio.exe" 
   0.002 Read data path: D:/Steam/steamapps/common/Factorio/data
   0.002 Write data path: C:/Users/andrew/AppData/Roaming/Factorio [75211/161707MB]
   0.002 Binaries path: D:/Steam/steamapps/common/Factorio/bin
   0.014 System info: [CPU: Intel(R) Core(TM) i7 CPU         860  @ 2.80GHz, 8 cores, RAM: 5974/12279 MB, page: 14520/28663 MB, virtual: 4327/134217727 MB, extended virtual: 0 MB]
   0.016 Display options: [FullScreen: 0] [VSync: 0] [UIScale: system (100.0%)] [MultiSampling: OFF] [Screen: 255] [Lang: en]
   0.017 Available display adapters: 1
   0.017  [0]: \\.\DISPLAY1 - AMD Radeon HD 5700 Series {0x8080005, [0,0], 2560x1440, 32bit, 60Hz}
   0.018 Create display on adapter 0. Size 1280x720 at position [630, 342].
   0.128 Initialised Direct3D:[0] AMD Radeon HD 5700 Series; driver: aticfx64.dll 8.17.10.1433
   0.136   Video memory size (dedicated video/dedicated system/shared system/available): 1010/0/3840/4092 MB
   0.219 DSound: Starting _dsound_update thread
   0.219 DSound: Enter _dsound_update; tid=5600
   0.220 Device reset internal.
   0.223 Desktop composition is active.
   0.223 Graphics settings preset: medium-with-low-vram
   0.224 Graphics options: [Graphics quality: normal] [Video memory usage: all] [Light scale: 25%] [DXT: auto] [Shader: 1]
   0.224                   [Parallel sprite loading: 1] [Max texture size: 4096/4096] [Bmp cache: 0] [Sprite slicing: 1] [Low quality rotation: 1]
   0.425 Loading mod core 0.0.0 (data.lua)
   0.448 Loading mod base 0.16.51 (data.lua)
   0.652 Loading mod base 0.16.51 (data-updates.lua)
   0.722 Checksum for core: 840319042
   0.722 Checksum of base: 3323233190
   0.853 Loading sounds...
   0.970 Info PlayerData.cpp:67: Local player-data.json unavailable
   0.970 Info PlayerData.cpp:70: Cloud player-data.json available, timestamp 1530619889
   1.118 Loaded shader file D:/Steam/steamapps/common/Factorio/data/core/graphics/shaders/game.cso
   1.118 Loaded shader file D:/Steam/steamapps/common/Factorio/data/core/graphics/shaders/zoom-to-world.cso
   1.119 Loaded shader file D:/Steam/steamapps/common/Factorio/data/core/graphics/shaders/alpha-mask.cso
   1.144 Initial atlas bitmap size is 4096
   1.151 Created atlas bitmap 4096x4081 [none]
   1.159 Created atlas bitmap 4096x4092 [none]
   1.163 Created atlas bitmap 4096x4094 [none]
   1.168 Created atlas bitmap 4096x4089 [none]
   1.172 Created atlas bitmap 4096x4076 [none]
   1.177 Created atlas bitmap 4096x4088 [none]
   1.178 Created atlas bitmap 4096x2457 [none]
   1.181 Created atlas bitmap 4096x4069 [terrain]
   1.181 Created atlas bitmap 4096x736 [terrain]
   1.181 Created atlas bitmap 4096x1943 [decal]
   1.209 Created atlas bitmap 4096x4076 [compressed, mask]
   1.229 Created atlas bitmap 4096x3312 [compressed, mask]
   1.260 Created atlas bitmap 4096x4096 [compressed, mask, shadow]
   1.278 Created atlas bitmap 4096x2808 [compressed, mask, shadow]
   1.287 Created atlas bitmap 4096x1392 [compressed, mask, smoke]
   1.287 Created atlas bitmap 4096x1868 [no-crop, trilinear-filtering, icon, light]
   1.287 Created atlas bitmap 4096x476 [alpha-mask]
   8.092 Sprites loaded
   8.092 Convert atlas 4096x4076 to: compressed 
   9.359 Convert atlas 4096x3312 to: compressed 
  10.491 Convert atlas 4096x4096 to: compressed 
  11.210 Convert atlas 4096x2808 to: compressed 
  11.658 Convert atlas 4096x1392 to: compressed 
  12.086 Convert atlas 4096x1868 to: trilinear-filtering 
  12.130 Convert atlas 4096x476 to: alpha-mask
  13.707 Custom inputs active: 0
  13.766 Factorio initialised
  27.998 Loading Level.dat: 859461 bytes.
  27.999 Info Scenario.cpp:136: Map version 0.16.51-0
  28.102 Checksum for script C:/Users/andrew/AppData/Roaming/Factorio/temp/currently-playing/control.lua: 950616531
  29.625 Device reset internal.
  64.339 Time travel logging:
  39.305 Player 0 ran command: game.player.teleport({-1000000, 0});
  53.140 Player 0 ran command: game.player.teleport({-1048000, 0});
  64.339 Player 0 ran command: game.player.teleport({-1048500, 0});
Factorio crashed. Generating symbolized stacktrace, please wait ...
c:\cygwin64\tmp\factorio-build-rlyqnq\libraries\stackwalker\stackwalker.cpp (924): StackWalker::ShowCallstack
c:\cygwin64\tmp\factorio-build-rlyqnq\src\util\logger.cpp (408): Logger::writeStacktrace
c:\cygwin64\tmp\factorio-build-rlyqnq\src\util\logger.cpp (521): Logger::logStacktrace
c:\cygwin64\tmp\factorio-build-rlyqnq\src\util\logging.cpp (89): Logging::logAndAbortOrThrow
c:\cygwin64\tmp\factorio-build-rlyqnq\src\surface\chunk.cpp (692): Chunk::Chunk
c:\cygwin64\tmp\factorio-build-rlyqnq\src\surface\surface.cpp (966): Surface::requestToGenerateAndActivateChunks
c:\cygwin64\tmp\factorio-build-rlyqnq\src\player.cpp (398): Player::update
c:\cygwin64\tmp\factorio-build-rlyqnq\src\map\map.cpp (1371): Map::update
c:\cygwin64\tmp\factorio-build-rlyqnq\src\game.cpp (163): Game::update
c:\cygwin64\tmp\factorio-build-rlyqnq\src\scenario\scenario.cpp (883): Scenario::update
c:\cygwin64\tmp\factorio-build-rlyqnq\src\mainloop.cpp (1007): MainLoop::gameUpdateStep
c:\cygwin64\tmp\factorio-build-rlyqnq\src\mainloop.cpp (874): MainLoop::gameUpdateLoop
c:\cygwin64\tmp\factorio-build-rlyqnq\src\util\workerthread.cpp (36): WorkerThread::loop
c:\program files (x86)\microsoft visual studio\2017\buildtools\vc\tools\msvc\14.12.25827\include\thr\xthread (232): std::_LaunchPad<std::unique_ptr<std::tuple<void (__cdecl RouterBase::*)(void) __ptr64,ServerRouter * __ptr64>,std::default_delete<std::tuple<void (__cdecl RouterBase::*)(void) __ptr64,ServerRouter * __ptr64> > > >::_Go
c:\program files (x86)\microsoft visual studio\2017\buildtools\vc\tools\msvc\14.12.25827\include\thr\xthread (211): std::_Pad::_Call_func
d:\th\minkernel\crts\ucrt\src\appcrt\startup\thread.cpp (115): thread_start<unsigned int (__cdecl*)(void * __ptr64)>
ERROR: SymGetLineFromAddr64, GetLastError: 487 (Address: 00007FFBE4153034)
00007FFBE4153034 (KERNEL32): (filename not available): BaseThreadInitThunk
ERROR: SymGetLineFromAddr64, GetLastError: 487 (Address: 00007FFBE5FE1431)
00007FFBE5FE1431 (ntdll): (filename not available): RtlUserThreadStart
Stack trace logging done
  66.231 Error Chunk.cpp:692: Trying to make chunk at unreasonable position [-32770, -4]
Logger::writeStacktrace skipped.
  66.231 Error CrashHandler.cpp:174: Map tick at moment of crash: 1916
  66.231 Error Util.cpp:67: Unexpected error occurred. If you're running the latest version of the game you can help us solve the problem by posting the contents of the log file on the Factorio forums.
Please also include the save file(s), any mods you may be using, and any steps you know of to reproduce the crash.
  70.443 Uploading log file
  70.447 Error CrashHandler.cpp:227: Heap validation: success.
  70.449 Creating crash dump.
  70.669 CrashDump success

[mrvn]

Well in my opinion the game still should not crash. By all means refuse to generate chunks outside the limit, but don't crash. (Don't forget that it is possible for players to disable the autosave, or set it to once an hour, so a crash could potentially mean that an hour or more of playtime building might be lost).

Just how expensive is the check, compared to the actual cost of generating chunks. Is the optimisation worth it?

Interestingly in testing this behaviour (after I wrote the above) I get different behaviour to that described by Mrvn. For me, attempting /c game.player.teleport({-1048550, 0}), causes a crash. Teleporting to -1048000,0 leaves be in a black space, which I imagine is outside the chunk generation boundaries. Teleporting to -1000000,0 leaves me right on the edge of that boundary, and the game won't let me walk left nor will it generate new chunks to the left. (0.16.51 Steam version, totally vanilla on Windows 10. Log below. I have no idea what the "time travel logging" is about).

Maybe an appropriate fix is for the teleport api to enforce the 1,000,000 tile limit that the chunk generator seems to obey.

No, that is the behavior I see.

Here the map generator will autoplace tiles within +/-1000000 tiles of the origin. Outside of that you still get chunks generated but not filled with anything. A simple black void. But the chunk is there. You can use landfill to place something. That's why I suggested simply to check for 1000000 on the teleport.

Note: You can also see this when you set the map size to 256x256. You get black void beyond that but landfill still works.

[eradicator]

Note: You can also see this when you set the map size to 256x256. You get black void beyond that but landfill still works.

No you can't. That void is actually "out-of-map" tiles. If you can place landfill there then you're using modded landfill with a broken collision_mask.

I have to agree with "don't crash just because the player did something stupid" though.

[Rseding91]

You are right, I don't know your code. But seriously? "overhead of doing the check"?

You already have a check in place. Just not a check against the right value. If you say the problem is extra chunks besides the one you land on then the right check is "if (x < 2^20 - MARGIN_BECAUSE_MORE_CHUNKS_GET_GENERATED)". That certainly has nothing to do with avoiding overhead. There is no cost increase there at all. That's not something that takes O(n^2) time or anything. It's one comparison for each direction. Now next you will say that the margin is variable so that isn't a constant anymore?

The overhead of adding checks to every bit of logic in the game that does "get chunk" having to check if the position is first valid and if not make sure all of the associated logic can handle it.

There is no excuse for a game crashing. Ever. It happens but don't excuse it, fix it.

Sure there is: we say generating a chunk past a given distance from 0,0 is an error and we terminate the game if you force it to do it some how.

[eradicator]

Sure there is: we say generating a chunk past a given distance from 0,0 is an error and we terminate the game if you force it to do it some how.

Nitpickingly speaking...the crash dialog does tell people to post the crash log to the forums. So...if you don't want us to actually post a log, then you're contradicting yourself. Can't you at least throw back to main menu instead of a full crash?

[Rseding91]

Sure there is: we say generating a chunk past a given distance from 0,0 is an error and we terminate the game if you force it to do it some how.

Nitpickingly speaking...the crash dialog does tell people to post the crash log to the forums. So...if you don't want us to actually post a log, then you're contradicting yourself. Can't you at least throw back to main menu instead of a full crash?

The point of that crash is to detect when things go wrong (division by zero requesting an entity move to negative infinity x/y) simply you can also force it to happen by moving things to the limits through script. Just like you can crash the game by doing: /c global.p = game.player.print; /c global.p("crash");

Simply don't do that. The overhead of having the game keep tail-chasing to prevent all of these things is not worth it compared to just telling people "don't do that".

[Rseding91]

After reading this over again I think I might have misunderstood part of your request: are you asking for *just* entity.teleport(...) to reject teleporting if it's outside the 1 million distance? I can change that without impacting the rest of the game logic.

[eradicator]

After reading this over again I think I might have misunderstood part of your request: are you asking for *just* entity.teleport(...) to reject teleporting if it's outside the 1 million distance? I can change that without impacting the rest of the game logic.

That's at least what i assumed he wants.
Too bad though, i just had this super-awesome idea to store some script-internal meta-entities in that inaccesible rim past 1M (mostly chests to work around the inability of storing ItemStack in the lua state).

[Zavian]

In my opinion, in an ideal world, nothing a player does, even with the help of the console or a mod should be capable of crashing the game. (From a players point of view logging an error and aborting without saving is basically equivalent to a crash). But I admit that is probably unrealistic.

I'd settle for restricting the teleport api to a value which does not crash the game. -1,000,000 works, but if modders want to be able to teleport items outside the play area for some purpose, then -1,024,000 would also work. (-1,048,000 does not crash the game for me, so I'm guessing -1,024,000 should be safe.

[mrvn]

Note: You can also see this when you set the map size to 256x256. You get black void beyond that but landfill still works.

No you can't. That void is actually "out-of-map" tiles. If you can place landfill there then you're using modded landfill with a broken collision_mask.

I have to agree with "don't crash just because the player did something stupid" though.

Then the landfill in Angles+Bobs has a broken collision_mask.

Sounds like out-of-map tiles should check better not to get replaced even if a collision_mask is broken. That would solve the "walking off the end of the world" part since then you can't get there. But that's independent from the teleporting function not checking for a small enough limit.