Hi,

My game is made in JavaScript and HTML5, but I'm looking for conceptual advice more than help with coding.

Currently I'm using a basic tile engine made from scratch, where each movement = 1 full tile worth of distance. Everything is working as intended, but I am looking to adopt a movement system similar to that in Secret of Mana, in the sense that movements are precise and not restricted to tiles. But truth be told, I'm not really quite sure what type of engine it uses. I assume it's a multidimensional array with much more cells than background tiles.


Currently I'm using a multi-dimensional array to keep track of my map data. Once loaded, the array is never updated based upon player or enemy movement. The array only keeps track of collidable and uncollidable background tiles.

Instead, to keep track of object positions, I'm using an array full of enemy objects. Each enemy has its own property that stores it's X and Y value.

The player also has its own property for X and Y.

As you can see, I don't have one big universal multi-dimensional array (is this the same thing as vector?) keeping tracking of all collision objects.

Currently for collision logic I am just comparing the moving object's X and Y properties to all other object's X and Y properties, and seeing if they match.

However, I would like to make my movements more precise, and less restricted to entire 1-tile movements.

I read online that one approach is to make one big vector with each cell being [0] or [1], representing empty or collidable respectively. I think this is a good approach, as I assume the only other option is to make fractional movements on my current tile system.

My question, though, is how many cells is should I actually make?

Each of my maps have say, 9 x 9 tiles, with each being 32px.

For the vector, would I really just make the cells (9 * 32) x (9 * 32), as in one cell per pixel?

I realize that would allow for very smooth and precise movements, but I wonder if that would be overkill. I imagine that looping over that many cells would be horribly expensive.

Is there a rule of thumb for deciding vector dimensions? Any personal experiences?

Am I even approaching this the right way?

How do I even describe what I am trying to do? I feel like I mis-titled my post!

Any insight on how Secret of Mana's system works?

Thanks!

No, the tiles you see in Secret of Mana (SoM), really are the size they look like, they just give the collision information and player movement more detail.

Lets say you have tiles that are 32x32, and a map of any size made up of those tiles. You can give players, enemies, and other non-tile objects in the game real pixel locations -- they don't have to move one whole tile at a time. To find out which tile your player is standing over, all you have to do is divide his position in pixels by the size of the tile -- so, if he's standing at 192, 128, then he's standing perfectly over tile 5,3 (in a 0-based coordinate space, like arrays). If, at another moment, he were standing at 208, 144, then he's standing over tiles 5,3; 6,3; 5,4 and 6,4. For collision, you have to check against all of the tiles he's partly standing over. If you have finer-grained collision data on those tiles, the he might be able to stand partly into a tile that he couldn't stand entirely on.

With whole-tile movement now, when you want to move into the next tile, you must be looking ahead at that tile (the one you want to move onto) and checking to see if you can move there or not. If the tile is open, you let the character move, and if its solid (like a wall, tree or barrel), you just don't allow the character to move. With pixel-based movement, its conceptually identical, you just check on a smaller scale -- When you want to move a few pixels, you "predict" or "project" where the character wants to be and you let him go there if there won't be any collision -- If there is collision, you either deny the movement entirely, or you allow them to move closer only by as much as they won't cause a collision.

Its a bit more complicated in this way only because there's more (and smaller-scale) information to consider, but its otherwise identical.

Hi Ravyne, thanks for the reply!

If I'm using pixel-precise tracking, why should I still check for my collision map in tile blocks? Since I have one cell for each pixel, shouldn't I just end up checking an area the size of my pending movement?

For example, say my sprite dimensions are 1x1 pixel. Each key input will move the characte 5 pixels, and I am moving the character to the right. Assuming no diagonal movements, shouldn't I only check on the collision map 5 cells to the right of me? I'm confused on why tile calculations should get involved, if I am keep pixel-precise coordinates and movements, and my collision map has 1 cell per pixel.

I think I got a bit away from part of what you were asking, which is how do you store the finer-grained collision data.

One way to do it, is to have a "collision map" for each tile -- just like they have a "texture map" that defined what they look like, they can have this collision map to do define their shape for the collision logic. This has the same benefits as tile systems do for graphics -- rather than one huge image of repetitious graphics taking up a lot of memory, you use tiles to save memory and re-use tiles as components of the whole map. Same thing with the collision map. Rather than a big vector, use collision map tiles to make the big collision map. Only conceptually though! You don't typically need to consider the whole collision map, just the little part that entities want to move into (and of course you need to do collision between entities too, but that's another story.)

Also, keep in mind that your collision maps don't have to match exactly the texture map. For example, if you have a tall box, you want to be able to walk "behind" it, but if your collision map had all the same pixels as the box, you'd only be able to walk "around" it. If you make the box shorter in the collision map, you'll be able to walk behind it (assuming you draw things in the correct order, or with z-depth)) -- really, what you're doing by drawing the collision box shorter, is drawing the part of the box that sits on the floor, so this makes perfect sense.

Another way to do collision is with real shapes -- boxes, circles, ellipses, triangles -- and this is often better, but it's considerably more complicated, and probably overkill for the kind of game you want to make, and your apparent skill level.

What exactly should each cell of my collision map look like? How are detailed is each cell's data? For example, is it a simple true/false (or 0/1) for collision? Or would it be plausible to have a key system in each cell as well, so that I know what object exactly is occupying that space?

In addition, how would I store a sprite's location on the map, if I am pixel-precise? Do I have an x/y coordinate for each corner of the sprite? Or do I just have an x/y coordinate for the middle of the sprite, and factor in the sprites width/height in the collison logic later?

Before I code this all out I'm really trying to get an idea in my head of all the components involved. Here is some pseudo-code of the components I envision:

-Map data (tile-based) stored in an array. Contains data for ground tile, and whether object is on ground. Not used in any collision logic. Only used to render the background and initialize the collision map.

[
    [ {"ground":1, "Object":1}, {"ground":1, "Object":1} ],
    [ {"ground":1, "Object":0}, {"ground":1, "Object":1} ],
]

// Ground Key
1 = grass

// Object Key
0 = empty
1 = barrel

-Collision map multi-dimensional array. Rows/collumns based upon the map data * 32 (the tile size). Ends up with 1 cell per pixel being used. Data is filled with either 0/1 for empty or collidable. Parse the map data. If tile object = 0, set all 32 cells in collision map to 0. If object != 0, set cells to 1, would the amount of cells corresponding to the actual pixel dimensions of that object's sprite. Using only 0/1 seems wasteful to me, but I've seen some other developer's do/suggest this, so I assume there must be a good reason why.

[  
      [  1, 1, 1, 0],
      [  1, 1, 0, 0]
]

// 4 cells per row
// 0 = empty, object can move here
// 1 = full, object cannot move here

-Array of entity objects (player, enemies, npc). Each object has x/y pixel-precise coordinates for every corner, OR for the middle of the sprite, but also keeps track of sprite's total width/height. Not used for determining collision, but used for attack logic later.

I think the main difference in implementing this is that instead of checking if an enemy's coordinate matches my player's pending movement, I match it against the collision map. But I feel like if I am commiting to make each pixel have its own cell, I might as well have the data in each cell represent the object occupying it, instead of just 0/1. Right? Doing so would certaintly save code when writing the attack logic.

After coding intuitively for most of this engine, all this help seems like candy to me :) Feels kind of like I'm cheating.

Thanks for your help!

As you can see, I don't have one big universal multi-dimensional array (is this the same thing as vector?) keeping tracking of all collision objects.

No it isn't. JS is a bit flexible with terminology so objects can work as arrays and are sometimes called "associative arrays". I'm still learning JS myself so I'm not even sure what a "vector" is supposed to be (vector and arrays are different things in C++ but that's another problem).

To have a multi-dimensional array, you need to put an array (aka object with consecutive integer-named properties) in another object property. Then you have two array indices to work with. Using a single array you would have to "split" it by yourself. This usually involves multiplying the "row" property by the amount of columns.

I realize that would allow for very smooth and precise movements, but I wonder if that would be overkill. I imagine that looping over that many cells would be horribly expensive.

But you don't need to loop them all - as said in the previous message, you could just look for specific pixels. I currently suggest to just have a "collision framebuffer" with the various collision masks; it sure won't be as clean as fully fledged solutions but I'd expect it to come at fairly lower effort.

Hi, maybe you are right about terminology being different across languages. I started using vectors synonymously with multi-dimensional arrays because I read some tutorials using 'vectors', and they looked the same to me. But it was with a language I'm not familiar with.

Can you elaborate on what you mean by collision framebuffer and collision masks? Is a collision mask just an object's corresponding part of the collision map? Thanks!

Hi all!

I'm resurrecting this thread as I need conceptual advice on how to implement a better drawpoint system.

Also I wanted to update about my project, so that you guys don't think your help went to waste

First off, please don't look at any of the actual code, since everything is messy and poorly written. I've learned a lot since I first started this project, and I haven't had the time to go back and clean up old code. So for now, please hold your criticism on actual code

Also everything is coded and tested on FireFox 23! I haven't made cross-browser considerations yet!

Here is my game with my original whole tile movement.

Here is my game with after implementing Ravyne's cell tile movement.

The system works nicely for drawing tiles, but I realized a few problems with its current implementation:

- I can only have one tile sprite per tile, regardless of that sprite's cell footprint

- Each sprite can only be drawn at the tile's origin (which I will later change from top-left to bottom-left)

Further more, in regards to the collision map, I realized that there is no real benefit in dividing the tile into cells, and then storing those cells into the tile. Instead of a map -> tile -> cell system, I should just use a map -> cell system. This way amount of calculations is reduced, as I only need to check the collision map for the adjacent cells.

I applied this reasoning when creating my level editor. *Note, magnification does not work, as I have not decided on my storage formats yet.

Currently, the data is exported as such:

[
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]

Drawpoints:
[
[1,168,112],[2,152,160],[3,104,80],[4,48,37],[3,48,80]
]

Draw Keys:
{"1":"tiles_bank_05","2":"tiles_bank_30","3":"barrel","4":"bucket-empty"}

Benefits of this sytem:

- Drawing tile sprites is fast, as pixel-precise drawpoints are already provided. No need for the client to find drawpoints, or do any tile to pixel calculations

The disadvantage of this system is:

- Keeping the order of the draw points is extremely critical. Since sprites are drawn top-down, if one drawpoint gets misplaced, sprites that exceed the width of the tile will start drawing over other sprites incorrectly.

- Inserting the player's sprite correctly into the chain of drawpoints is extremely complicated, especially when you factor in player movement.

It is for the above disadvantages that I am abandoning this system.

I considered simply embedding the drawpoints into the cells of the collision map. But that would mean that to draw the sprites, I would have to loop through every cell of the collision map and find out which cells contain drawpoints. And a collision map of 16x16 32px tiles (consisting of 4x4 cells) would have 4096 cells...

So that doesn't work.

My most recent idea is to keep my current boolean collision map system, but also keep a seperate tile-based map just for tile draw points. It is basically the system I used when in my implementation of Ravyne's suggestion. But if I want to allow for more than one sprite per tile, or precise positioning of that sprite within the tile, I will need complex tile data. Complex tile data that might necessitate dividing each tile into a 4x4 cell map, which puts me in the same position as the above method...

*EDIT* Actually, I thought about how I would format such tile data, and it would be something like:

// Tile 1
[
[ "barrel", tileSize / 4, tileSize / 4], // elements [1] and [2] are the x/y offesets relative to the tile.  Offsets the sprite by 1/4 x 1/4
[ "barrel", tileSize / 2, tileSize / 2] // Offsets the sprite by 1/2 x 1/2
 ]

This sytem would allow for multiple sprites per tile as well as offsets, without needing the inclusion of cells!!! Also, because the tile map will always be traversed in the same order, there is no risk of out-of-order sprite drawing! Any thoughts on this format?

I'm going to spend some time to think of possible caveats before actually implementing this. Don't want to implement a flawed system for the 5th time!

Please give me advice on better system that allows for precisely determining tile sprite drawpoints!

Also regarding the collision mask vs collision map discussion:

I created a handy little tool that converts an image like:

Into:

[
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
]

Which is then scaled to:

[
[0,0,0,0,0,0,1,1]
[0,0,0,0,1,1,1,1]
[0,0,0,1,1,1,1,1]
[0,0,0,1,1,1,1,1]
[0,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1]
]

[
[0,0,1,1]
[0,1,1,1]
[1,1,1,1]
[1,1,1,1]
]

So once I implement this algorithm into my current level editor, my collision map should be faithful to each sprite's shape.

A simple way to solve this (but not as precise as Khrom's method) is have four points that form a box around the character, in other words, if you character is 32 x 32 and its position is giving by the bottom lower point of it, and it is on position (64, 64) you save four points:

Bottom-left = (64, 64), Bottom-right = (96, 64), upper-left = (64, 96) and upper-right = (96, 96).

When you move him 5 units to the right, as the example you gave, you add 5 in the x axis:

Bottom-left = (69, 64), Bottom-right = (101, 64), upper-left = (69, 96) and upper-right = (101, 96).

You convert every point to tiles coordinates and check if any of the tiles is occupied, if it is, you restrict the movement, if it isn't you move the character.

If I where you I would take a look at this lib:

http://box2d-js.sourceforge.net/

It is a port of box2d for JS, you can use it to detect collisions, it will be slower than the tile detection method I suggested, but much easier to use and also will allow you to have multiple size/form objects in your scene.

PS: Your scene looks really great, keep it up.

Thanks for your reply!

I actually thought of a similar idea of using corners at first, but then I realized that I don't need the top left and top right corners of the sprite. Using them would actually prevent the player from moving 'in-front' of anything. Instead, I took the four points to create the dimension of the 'feet', and then did all collision detection based upon the feet, which allowed my character to 'stand in-front' of objects.