News: 11 March 2016 - Forum Rules

Author Topic: Final fantasy (NES) torus map algorithm  (Read 2793 times)

Lloyd2k4

  • Jr. Member
  • **
  • Posts: 4
    • View Profile
Final fantasy (NES) torus map algorithm
« on: June 16, 2016, 12:14:05 pm »
Hello everyone,

Im looking for anyone who has exerience modding or dealing with any game that has a torus algorithm implemented in order to wrap its 2d tile maps.

An example of a game that does this is the original final fantasy on the NES.

Im trying to develop a similar algorithm to replicate this feature in a stand alone original project, but im not having much luck.

If anyone knows anything about this subject or knows how some old school games implemented it, I would surely appreciate listening to what you have to say!

I apologize for my lack of grammar. Im posting this from my android browser so I cant type as well as I normally would.

tryphon

  • Hero Member
  • *****
  • Posts: 737
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #1 on: June 16, 2016, 12:33:28 pm »
What's the difficulty exactly ?

Disch

  • Hero Member
  • *****
  • Posts: 2814
  • NES Junkie
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #2 on: June 16, 2016, 12:44:14 pm »
Retro games do this by wrapping the X and Y coordinates.  Usually by restraining them to a certain number of bits.

In Final Fantasy's case, the world map has 8-bit coordinates, while other maps have 6-bit coordinates.

This means the world map is 256x256 (28), and will wrap FF<->00
And other maps are 64x64 (26), and will wrap 3F<->00


Wrapping in this case is as simple as an AND operation:

Code: [Select]
// in C:
x = x & 0x3F;  // wrap at 6 bits

// in 6502
LDA x_coord
AND #$3F
STA x_coord

Lloyd2k4

  • Jr. Member
  • **
  • Posts: 4
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #3 on: June 16, 2016, 01:50:28 pm »
Disch, you are a savant. Thank you so much!  I just tested your code in a java for loop trying 2^9 (512) and it properly loops back to zero after hitting 511. Anything that isnt a perfect bit constraint 2^n doesnt work properly and seems to do a looping pattern with the remainder from the closest bit, but anything that is a valid bit constraint 2^n where n is any integer, works.

I had no idea it was this simple.

Disch

  • Hero Member
  • *****
  • Posts: 2814
  • NES Junkie
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #4 on: June 16, 2016, 03:20:26 pm »
Yeah with the bitmask approach it has to be a power-of-2 to ensure the mask has all relevant bits set.

Example
Code: [Select]
width of 256:   256-1 = 255 = $FF = %11111111   <- mask has all 1's
width of 100:   100-1 =  99 = $63 =  %1100011  <- mask has some 0's, so it'll be screwed up

If you don't want a power of two, you can use the modulo which has more or less the same effect, but doesn't play as nice with negative numbers:

Code: [Select]
// want a width of 100:
x = x % 100;

Modulo effectively gives you the remainder after a division.  So if 'x' is 537 going into the above code, 537 / 100 is 5 with a remainder of 37.  So 537 % 100 = 37, effectively performing a wrap at the 100 bound.


The problem is modulo is ill-defined for negative numbers.  For purposes of wrapping, you would want (-1)%100 to give you 99... but it might not depending on the implementation.  I'm not sure how Java does it, but in C it's very much a "do not do this ever" situation.

You can be a trickster with math, though.  Example, 1%100 is 1.  And 100-1 is 99.  So:

Code: [Select]
// to wrap with negative support
int width = 100;  // <-wrap at 100

// to wrap at 100 (with negative support)
if(x >= 0)
{
    // positive number, normal modulo works
    x %= width;
}
else
{
    // negative number
    x = width - (-x % width);  // this uses the above trickster logic
            // x=-1  ....  -x    ->  1
            //          % width  ->  1
            //          width -  -> 99
           
    // however this will not completely work for multiples of width.
    //   Ex:   x=-100  ... -x    -> 100
    //                % width    -> 0
    //                width -    -> 100   (we want 0, not 100)
   
    // So we can do a final check here
    if(x == width)
        x = 0;
}

Another solution is to just ensure that you NEVER have a negative x... in which case you can just use modulo.

In any case, you can see how this is more work and more error prone, which is why wrapping maps on retro consoles pretty much were always power-of-2 sizes.  It just makes them easier to work with.

Lloyd2k4

  • Jr. Member
  • **
  • Posts: 4
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #5 on: June 16, 2016, 11:47:37 pm »
So, I'm encountering an issue on where exactly I need to place this code.  I've been trying different areas in my World class, and can't figure out if I need to put it in the loading routine, the render routine, or both.  So far, everything I've tried has resulted in no change. :angel:

My guess is I may need to re-engineer the way my World class works in order to get this to work properly.

Code: [Select]
public class World {

protected Handler handler;
private int width, height;
private int spawnX, spawnY;
private int[][] tiles;

private EntityManager entityManager;

/**
* Generic World constructor
* @param handler
* @param path
*/
public World(Handler handler, String path){
this.handler = handler;
loadWorld(path);
// TODO: need to not hardcode this but rather go based on the top most job of the player party later on, also
// need to make a facing up sprite and a facing down sprite, and eventually an animation walking sprite
BufferedImage[] sprites = new BufferedImage[] {Assets.getTile(7), Assets.getTile(8), Assets.getTile(9), Assets.getTile(10)};
entityManager = new EntityManager(handler,
new Player(handler,spawnX * Constants.DEFAULT_WIDTH,spawnY * Constants.DEFAULT_HEIGHT,Constants.DEFAULT_WIDTH, Constants.DEFAULT_HEIGHT,sprites));
}
/**
* This method ticks all the entities within this World.
*/
public void update(){
entityManager.update();
}
/**
* This method renders the map, but will only render the tiles that are within our camera's field of view
* plus a little extra
* @param g - Graphics object
*/
public void render(Graphics g){
int xStart = (int) Math.max(0, handler.getGameCamera().getxOffset() / Constants.DEFAULT_WIDTH);
int xEnd = (int) Math.min(width, (handler.getGameCamera().getxOffset() + handler.getWidth()) / Constants.DEFAULT_WIDTH + 1);
int yStart = (int) Math.max(0, handler.getGameCamera().getyOffset() / Constants.DEFAULT_HEIGHT);
int yEnd = (int) Math.min(height, (handler.getGameCamera().getyOffset() + handler.getHeight()) / Constants.DEFAULT_HEIGHT + 1);
// render each tile within the calculated camera view
for(int y = yStart; y < yEnd; y++){
for(int x = xStart; x < xEnd; x++){
getTile(x,y).render(g, (int)(x * Constants.DEFAULT_WIDTH - handler.getGameCamera().getxOffset()),
(int)(y * Constants.DEFAULT_HEIGHT - handler.getGameCamera().getyOffset()));
}
}
entityManager.render(g);
}
/**
* This method will return the actual Tile object which contains the image
* and any tile specific data based on the id stored in the tiles[][] 2d array.
* This is both null safe and out of bounds safe; it will return a default tile
* in either case.
* @param x - x tile coordinate
* @param y - y tile coordinate
* @return - Tile object to be rendered at x,y (in tiles, not pixels)
*/
public Tile getTile(int x, int y){
if( x < 0 || y < 0 || x >= width || y >= height )
return Tile.tiles[0];

Tile t = Tile.tiles[ tiles[x][y] ];
if(t == null)
return Tile.tiles[0];
else
return t;

}
/**
* This method will load the world file from a text file and tokenize it
* , then apply the necessary data to this World object.
* @param path - the path to the resource text file.
*/
private void loadWorld(String path){
String file = Utils.loadFile(path);
String[] tokens = file.split("\\s+");
// the first few tokens will always be this data
width = Utils.parseInt(tokens[0]);
height = Utils.parseInt(tokens[1]);
spawnX = Utils.parseInt(tokens[2]);
spawnY = Utils.parseInt(tokens[3]);
// begin allocating the tile id's for each tile of the map
tiles = new int[width][height];
for(int y = 0; y < height; y++){
for(int x = 0; x < width; x++){
tiles[x][y] = Utils.parseInt( tokens[(x + y * width) + 4] );
}
}
}
}

Also, I found this little stackoverflow of the whole modulo operator discussion for the purpose of this:

http://stackoverflow.com/questions/30698661/java-2d-array-making-it-torus-like

Disch

  • Hero Member
  • *****
  • Posts: 2814
  • NES Junkie
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #6 on: June 17, 2016, 09:58:54 am »
So, I'm encountering an issue on where exactly I need to place this code.

My first thought:
Code: [Select]
public Tile getTile(int x, int y){
if( x < 0 || y < 0 || x >= width || y >= height )
return Tile.tiles[0];

First thing getTile does is checks to make sure the tile is in bounds.  However, if you wrap the coordinates, you'll always be in bounds.

Though if you do that, you'll probably want to use getTile everywhere (even within the World class) to access the tiles array.  That is, no other method should directly touch it (other than construction -- or places where you know the coords will always be in bounds).

Lloyd2k4

  • Jr. Member
  • **
  • Posts: 4
    • View Profile
Re: Final fantasy (NES) torus map algorithm
« Reply #7 on: June 17, 2016, 02:35:12 pm »
Disch, I had already tried there and it didn't work, BUT you are correct that it is supposed to go there.  I figured out *why* it wasn't working even though it is supposed to be there.

It was in my render() method for the World:

Code: [Select]
int xStart = (int) Math.max(0, handler.getGameCamera().getxOffset() / Constants.DEFAULT_WIDTH);
int xEnd = (int) Math.min(width, (handler.getGameCamera().getxOffset() + handler.getWidth()) / Constants.DEFAULT_WIDTH + 1);
int yStart = (int) Math.max(0, handler.getGameCamera().getyOffset() / Constants.DEFAULT_HEIGHT);
int yEnd = (int) Math.min(height, (handler.getGameCamera().getyOffset() + handler.getHeight()) / Constants.DEFAULT_HEIGHT + 1);

Changed to:

Code: [Select]
int xStart = (int) handler.getGameCamera().getxOffset() / Constants.DEFAULT_WIDTH - 1;
int xEnd = (int) (handler.getGameCamera().getxOffset() + handler.getWidth()) / Constants.DEFAULT_WIDTH + 1;
int yStart = (int) handler.getGameCamera().getyOffset() / Constants.DEFAULT_HEIGHT - 1;
int yEnd = (int) (handler.getGameCamera().getyOffset() + handler.getHeight()) / Constants.DEFAULT_HEIGHT + 1;

The min and max methods were restricting everything because it was never allowing anything beyond the bounds of the map to render.

And here's what I added to getTile() just for reference:

Code: [Select]
public Tile getTile(int x, int y){
x = (x % width + width) % width;
y = (y % height + height) % height;

Tile t = Tile.tiles[ tiles[x][y] ];
if(t == null)
return Tile.tiles[0];
else
return t;
}

It appears the formula used in that stackoverflow method above works fine.