1
\$\begingroup\$

I love this procedural generation theory and have been messing around with it. However I'm having trouble wrapping my head around how to store my map data. Usually I store my map data in a 2d array and that works in a limited space. However my map grows as the player explores new territory. So the size of the map changes and what's more the array will only support positive indices. So if the player tries to explore west or north he runs into a black abyss of nothingness. But I what more map to generate in those directions. Unfortunately those are the negative coordinate parts of the map. Is there a way to support a negative coordinate as the player explores new area? Here is an example of the problem in action.

https://76295db93db3812642fa5ba984c042fa81ffc37c.googledrive.com/host/0B6H3TRExU5M9eEkyd2FreHhiNlU/

Try moving West or north and you'll run into the edge of the map.

\$\endgroup\$
1
\$\begingroup\$

You need to handle your map in chunks/tiles of fixed size.. and only keep the chunks in the immediate vicinity of your player actually on hand at any moment (out to whatever view distance you feel is reasonable)

As the player crosses a chunk boundary, you add new chunks in the direction of movement, remove them behind the player, and keep going.

If you are working on a truly endless world (or at least endless in terms of the scale of double precision coordinates) then you need to setup a system that does its best to keep the camera fairly close to the scene/world origin... I've handled this in one of my own tech demos by layering a double precision positioning system on top of the typical float positioning in most game engines... when the player moves in the world, every so often the camera will offset the float positions of everything such that the camera is close to 0,0,0 in world space coords

This is called a Camera Centric positioning system and is about the only sane way to handle large terrain spaces or even solar systems where you want to have accurate coordinates even for things that are too far away to be currently visible.

\$\endgroup\$
  • \$\begingroup\$ How can I use my negative coordinates? Would I store that in an array? \$\endgroup\$ – zachdyer Sep 8 '14 at 4:50
  • \$\begingroup\$ I started my screen drawing loop with the map x and map y coordinate and that supported drawing out the north and west areas of the map. \$\endgroup\$ – zachdyer Sep 8 '14 at 5:40
  • \$\begingroup\$ Within a chunk, where your fixed size array of terrain data is located, all coords are positive... where you render that chunk in the scene can be anyplace positive or negative -- in your chunk container you keep an array of chunks that you shift left/right/forward/back as the player moves around and fill in the edges with new chunk data at the correct position in the scene \$\endgroup\$ – Ascendion Sep 9 '14 at 1:06
  • \$\begingroup\$ I added the chunks and it helps with the processing speed. However I opted to go ahead and support negative coordinates because it seems to work right out of the box. Are there any problems I need to worry about doing it this way? \$\endgroup\$ – zachdyer Sep 15 '14 at 19:17
0
\$\begingroup\$

Most important thing i see about your issue is to keep a good separation of concerns.
When you wonder about 'negative array indexes', you have an issue because you mix the concern of knowing where the player is, and the concern of how you build/store your world data ('map').

Have a camera object, that will define what is the center of the current view and a view scale (zoom). The canvas + the camera gives you a view port : on each render, you can easily compute the viewable rectangle in world coordinates.
Now, give your World an interface that uses only world coordinates: Now you're freed from the index issue, you can move/copy/... the array(s) that represent your world without breaking anything in your game.

The best way to model the world depends on your game : can the user come and go anywhere ? Is the map only horizontal/vertical, do objects re-spawn, ...???

I the general case, you can use a fixed-size array that covers, say, 4 times the screen.
Handle a offset on x and y : that would be the center of the array (two indexes, centerIndexX, centerIndexY), and the related world coordinates (centerX, centerY).
Rough pseudo-code :

   function drawWorld(camera) {
      // if the view rect does not intersect the stored part of the world...
      if (!intersect(camera.rectangle, world.rectangle) {
         world.generate(camera); // generate a view centered on the camera
      }
      // where is the camera within the world ?
      var tileRatioX     = ( world.centerX - camera.centerX ) / word.tileSize;
      var tileOffsetX    = Math.floor(tileRatioX);
      var tileRemainderX = tileRatioX - tileOffsetX;
      tileOffsetX       += world.centerIndexX ;
      // ... same for y
      // compute width/height of the view in tiles
      var tileHalfWidth = Math.floor(0.5*(camera.width) / word.tileSize);
      // same for height
      // draw
      for (var i=tileOffsetX-tileHalfWidth, ix=0; i<tileOffsetX+tileHalfWidth; i++, ix++) {
           for (var j=tileOffsetY-tileHalfHeight, jy=0 ; tileOffsetY+tileHalfHeight ; j++, jy++) {
              var currentTile = world._tileArray[i][j];
              // draw CurrentTile at (ix,iy)*tileSize + (tileRemainderX,tileRemainderY)
           }
      }
  }
\$\endgroup\$
0
\$\begingroup\$

You can build a graph data structure to handle the changes between chunks.

Depending on exactly how you want the chunk boundaries to work, you may or may not need to render more than one chunk at a time. Many games have chunk boundary hallways that are Z or other sight-line blocking shapes. These are so that the game can fresh load the next chunk before you get there.

If your terrain is generated in a deterministic way (after random seeding maybe) you could just regenerate it as the player walks around and not even have to keep a record of it, so your 2D array would always be just a bit larger than the map (to allow monsters to be one or two tiles off the edge).

Example:

if (playerX < 0)
    nextChunk = currentChunk.westChunk
    if (nextChunk == null)
        nextChunk = new Chunk()
        nextChunk.eastChunk = currentChunk
        currentChunk.westChunk = nextChunk
    currentChunk = nextChunk
    playerX = currentChunk.maxX

With the above pseudocode, you only create new chunks when the player reaches them but they stay in place if the player ever goes back. You'd need to do the other directions as well of course, but this should give you a start.

Looking at the code behind your site, I think that what you call map is the same thing we're calling chunk, except chunk has a few more properties to connect to each other. Your map drawing code could either deal with neighboring chunks, or more easily only display one chunk at a time.

\$\endgroup\$
  • \$\begingroup\$ Since I'm using javascript I decided not to use a random seed generator and am only using Math.random. However I'm interested in using a seed generator because of the fact I could save on storage. \$\endgroup\$ – zachdyer Sep 8 '14 at 19:54
  • \$\begingroup\$ check out this stack overflow question for how to use Math.random with a seed \$\endgroup\$ – Eben Sep 8 '14 at 19:58
  • \$\begingroup\$ Would the graph data structure be an array of chunks and the chunks would have the tile data? \$\endgroup\$ – zachdyer Sep 8 '14 at 20:57
  • \$\begingroup\$ The graph structure wouldn't be an array at all. You'd have a Chunk object that had a property westChunk that is a reference to the next chunk to the west, for example. Because there's no array then there's no index to worry about being negative. \$\endgroup\$ – Eben Sep 8 '14 at 21:17
  • \$\begingroup\$ Would it be like new Chunk(0,0) and i would have chunk.x = 0 and chunk.y = 0 and it would loop over the Chunk(0,0).data[x][y]? \$\endgroup\$ – zachdyer Sep 8 '14 at 21:37
0
\$\begingroup\$

For situations like this where I want an endless map with possibly negative coordinates, I use a hash table instead of an array. In JS, the easiest thing (maybe not the cleanest) is to use an Object:

function Map() {
    var contents = {};

    function index(x, y) {
        return x + "," + y;
    }

    function set_map(x, y, value) {
        contents[index(x, y)] = value;
    }

    function get_map(x, y) {
        return contents[index(x, y)];
    }

    return {get: get_map, set: set_map};
}

var m = new Map();

Negative coordinates work just fine in this system. For example, after running m.set(-3, 5, 'A'), the map contents will be { '-3,5': 'A' }. You can call m.get(-3, 5) and it will return 'A'. Anything that isn't defined in the map will return undefined. And any parts of the map that haven't been explored yet won't take up space in the map.

\$\endgroup\$
  • \$\begingroup\$ Not sure why but for some reason my negative coordinates are working as an array in JavaScript. map.data[-1][-10] seems to work just fine. I thought I couldn't use an array to do that. \$\endgroup\$ – zachdyer Sep 9 '14 at 3:26
  • \$\begingroup\$ Ah, cool. Just be careful — some of the methods like slice() behave differently when given negative indices. \$\endgroup\$ – amitp Sep 9 '14 at 5:01
  • \$\begingroup\$ Any other problems I may run into using negative indices? \$\endgroup\$ – zachdyer Sep 10 '14 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.