Storing 2d terrain for a game

alextheinfinite

Hello,

I am making a game, and I was wondering how I should store the terrain.

My Idea was to make two 2d-arrays. Both would be of class "tile" with many sub classes such as "dirt" or "stone". The first array will contain the original terrain, while the second will contain player-updated terrain. This way I can reload a tile if the player deletes something. I would also be able to differentiate the tiles by using objects.

I want to know if there is a more efficient way to store the terrain, that allows for player-modifications to be undone.

Thanks

quark

Depends what you mean by player-updated terrain, for instance if it was blood splaces make a tile with a transparent background and red blood. Then simply display over the existing tile.

alextheinfinite

I wont have any decals on the terrain. I meant if the player wants to replace a block with a different one. In my case, the player is a plant. If they grow roots in the ground, and later delete them, I need a way to know what to replace the root tile with.

MenteCode

I'm pretty confident that outside of the paranormal code wizardry that I haven't been a part of yet, the most efficient way to store an undo-able terrain is to only store the starting terrain.

Then, when you move along, and tiles change, you simply store the location of the changed tile (x, y), and what the previous tile was. You'd most likely use an ArrayList here.

This way, you don't have to store the entire terrain, most of which will not have changed. If you want to undo whatever change to the terrain, you just look at the most recent entry, and replace the tile again.

alextheinfinite

That helps a lot, thank you!

blindfish

I remember using an image to store terrain data a while back: using greyscale images as a height map isn't uncommon. That obviously doesn't apply to a 2d game, but I vaguely remember also using images to store the location of different objects on the terrain: colors can be accessed as an int and different int values associated with different objects.

That's probably woefully inefficient for use during play (parse the image into an array during setup!); but it's really convenient to be able to throw map data together using an image editor!

alextheinfinite

I thought of that as well. I want a random terrain, so I can not use an image editor. I was thinking of saving the frame after generating the terrain, and using that. I decided not to because it is easier to run polymorphic functions on the objects in a 2d array.

I was also wondering how I can generate gravity for the objects in the user-influenced array. it seems very hard to me to take all of the objects in the array, find the center of gravity, weight, and change coordinates accordingly.

Any good ideas on that?

asimes

If any particular square has a history that can only be undone then what you need per square is a stack

If you are not familiar with a stack the basic idea is that it is a data structure that supports push() and pop(). In your case the stack for each square would start with one element which is whatever that square originally was. Lets say that visually it looks like this:

Stack -> { Original Element }

When that square changes you call push() which adds a new element to the stack. Visually it would now be this:

Stack -> { Original Element, New Element }

If it changes again then you would call push() again:

Stack -> { Original Element, New Element, Newer Element }

If you wanted to undo one step of history then you would call pop():

Stack -> { Original Element, New Element }

If instead you had wanted to remove all history then you would have instead called pop() until only the original element remains

You could implement this in Processing by having an array of ArrayList where the ArrayLists are acting as stacks. Below is a sketch that represents the current state of each tile with an int. Clicking on a square in "Push Mode" pushes a new state to that square. Clicking on a square in "Pop Mode" undoes one step of history (unless that "Stack" only has one element). Press 'u' or 'o' to toggle "Push Mode" and "Pop Mode" respectively

final int WIDTH = 30;
final int HEIGHT = 20;
ArrayList<Integer>[] tiles;
boolean pushMode = true;

void setup() {
  // WIDTH * 20 is 600 and HEIGHT * 20 is 400 
  size(600, 400);

  // Create an array with WIDTH*HEIGHT elements (600 elements)
  tiles = (ArrayList<Integer>[])new ArrayList[WIDTH*HEIGHT];

  // Initialize each ArrayList to some number of elements
  // Each will have at least one element
  // Some will have more than one element
  for (int i = 0; i < WIDTH*HEIGHT; i++) {
    tiles[i] = new ArrayList<Integer>();
    int randomValue = (int)random(1, 10);
    for (int j = 0; j < randomValue; j++)
      tiles[i].add(j+1);
  }

  println("Push Mode");
}

void draw() {
  background(255);

  // Display what tile the mouse will affect if it is clicked
  fill(255, 0, 0);
  rect(mouseX/20*20, mouseY/20*20, 20, 20);

  // Display the state of each tile
  fill(0);
  for (int i = 0; i < WIDTH; i++)
    for (int j = 0; j < HEIGHT; j++) {
      int index = i+j*WIDTH;
      ArrayList<Integer> currStack = tiles[index];
      text(currStack.get(currStack.size()-1)+"", i*20, j*20+12);
    }
}

void mousePressed() {
  // Get the "Stack" the mouse is hovering over
  int index = mouseX/20+mouseY/20*WIDTH;
  ArrayList<Integer> currStack = tiles[index];

  // If in "Push Mode" then add a new element to the current "Stack"
  if (pushMode)
    currStack.add(currStack.get(currStack.size()-1)+1);

  // If in "Pop Mode" then remove an element from the current "Stack"
  // Only do this if the current "Stack" has more than one element
  else if (currStack.size() > 1)
    currStack.remove(currStack.size()-1);
}

void keyPressed() {
  if (key == 'u' || key == 'U') {
    if (!pushMode)
      println("Push Mode");
    pushMode = true;
  } else if (key == 'o' || key == 'O') {
    if (pushMode)
      println("Pop Mode");
    pushMode = false;
  }
}

If you have questions let me know, I know that some of the array / ArrayList syntax is weird / ugly

alextheinfinite

I like this method much more. Its too bad java doesn't support stacks. I come from a c++ background with implemented vectors and stacks.

At first, I though that having an array in each slot would take too much space and time, but it seems to work very well. Thank you for making that example. This will make it easier to find which tile to undo.

asimes

I just realized now after writing the code that I didn't actually implement push() or pop() anywhere, I just did a pseudo implementation without classes that works similarly to what I had described, I hope that is not confusing

To actually call push() / pop() you could make a class which stores an ArrayList and has push() / pop() methods. You could call it say "Tile" and that class would store an ArrayList which represents its history. It could also have the methods push() and pop() which perform the history functions I did implement above. Whatever else you would like to associate with your squares would belong in the "Tile" class

alextheinfinite

Yeah, I have made a stack class in the past. I can just copy that code.

I would also use a 2d array list so I can directly use the array positions for position on the screen.

asimes

2D declaration, initialization, and iteration as an example:

final int WIDTH = 30;
final int HEIGHT = 20;
ArrayList<Integer>[][] tiles;

void setup() {
  size(600, 400);
  fill(0);

  tiles = (ArrayList<Integer>[][])new ArrayList[WIDTH][HEIGHT];

  for (int i = 0; i < WIDTH; i++)
    for (int j = 0; j < HEIGHT; j++) {
      tiles[i][j] = new ArrayList<Integer>();
      int randomValue = (int)random(1, 10);
      for (int k = 0; k < randomValue; k++)
        tiles[i][j].add(k+1);
    }
}

void draw() {
  background(255);
  for (int i = 0; i < WIDTH; i++)
    for (int j = 0; j < HEIGHT; j++) {
      ArrayList<Integer> currStack = tiles[i][j];
      text(currStack.get(currStack.size()-1)+"", i*20, j*20+12);
    }
}

alextheinfinite

I just learned that ArrayLists do not support extended classes. I think I will make each of those ArrayLists a normal array, since I want a set dimention

alextheinfinite

Never mind what I said in the last comment, I was trying to use [i][j][arrayPosition] instead of the add, remove, and get functions

koogs

Its too bad java doesn't support stacks.

there's a Stack interface but it is now considered legacy software and you should use Deque instead.

http://examples.javacodegeeks.com/core-java/util/deque-util/java-util-deque-example/

alextheinfinite

Oh, there are double ended queues! But the problem with that is you can't access a variable in the middle. I think the ArrayList that asimes used is the exact same as a stack, just with different syntax.