Ok... maybe I overdid it a bit with the subject. Here''s what this thread is about. Say that a isometric tile is 32x16 and that your map engine supports multiple object to be located over the same tile AND on offsets within the tile. How would you handle objects that are too big for the tile that they are over? There are a few possibilities that I can think of. 1) Every tile that the object covers has a pointer back to that object. So if object A covers 5 tiles, then all 5 tiles have pointers back to that object. Not a bad solution except keeping track of the object can be a pain when it moves. 2) Break the object into smaller pieces that would fit on a single tile. I personally don''t like this idea. I think it would bring up way too much extra work. 3) Ignore the first way and just have one tile (the one that it''s origin is over) contain the pointer. The problem with this one is that in order to do collision checking to see if you can walk onto a tile, you need to check the tile in question and all the tiles around it upto the maximum number of tiles that any 1 object can span. This too can be a pain in the rectal orifice also. What do you think oh great and knowledge isometric programmers of legends? Dino M. Gambone
Good judgement is gained through experience. Experience, however, is gained through bad judgement.

OMG! This is totally insane. I was just about to place a new thread on how to collision detection for objects larger than my 32x32 map tiles!!! I swear...very weird my friend.
I was thinking to myself, say i want to build a catapult in the future which would be way larger than 32x32..like 160x192. I think i have the math worked out so the "image" can be placed according to tile and offset but i get into problems when i have a player walking anywhere up to 2 tiles away from this catapults tile.
a) no way in hell am i breaking up my animation/bitmaps for objects into seperate squares...the graphic artist(me) will quit! hehe.

b) i had the same idea and check ALL objects in surrounding tiles by an area the size of the largest object in my world. This is doable as you say...just more work.

Those i came up with, then you mention a possible "list" of pointers in a tile to all objects from other tiles. There may be ways to make this work as well. So for either of these last 2 are all i can figure out to work out fairly easy.
If this was chosen, each time that object moved you would have to loop through each tile this object moves over. And do a pointer list insert and then a pointerlist delete when the object moved.

Unfortunately i have just come to the realization of larger than tile size objects..ill post if i brainstorm anything new like a supporting structure of larger objects, etc. 8)

aka John M.
Never give up. Never surrender!

Wasnt there something in the tile based games faq about this?

Hmm.. I''ve thought of something. This may not be the best solution.. or even a solution at all, but it sounds like it could be useful.

Let''s say the standard isometric tile will be 32x32. Now, if a tile is added to the map that is larger than that size, then it will "split" that tile up into different coordinates (it''s explicit coordinate, and all the coordinates it overlaps into). For example, let''s say you add a tile of size 64x64 to the map at the location (0, 0). Then this tile would now cover these coordinates: (0, 0), (0, 1), (1, 0), (1, 1). So we now know which coordinates this tile will fit on. Now where you go from here is up to you, but one possible solution would be to make some sort of list of a structure that looks something like this:

struct TILE_POINTER
{
int x, y;
int px, py;
};

Note that there would only be one list for the whole map. For the example above, there would be these values in the list:

list element 0: (x = 0, y = 1), (px = 0, py = 0)
list element 1: (x = 1, y = 0), (px = 0, py = 0)
list element 2: (x = 1, y = 1), (px = 0, py = 0)

Note that the (0, 0) coordinate wasn''t included because it would be redundant.

Now whenever you check for a collision at a certain location, you check the list to see if the location matches a (x, y) pair in a list element. If so, it is colliding with (px, py) of that element. Also note that this method will become very slow if there are many "large" objects in the map.

Perhaps a better way would be to give each coordinate on the map a list of these TILE_POINTER structures. Anyway.. Hope that helps =]

- Ian Perez (fett@willcomp.com) - "It is by will alone I set my mind in motion"
- Majick Studios (www.willcomp.com/majick)

First off, you have to make the tiles as small as possible so that a tile becomes the smallest possible segment of movement. That means that you do not have offsets with in a tile. An object is either in a tile, or not, there is no offset with in a tile. If you do have offsets, then you must make your tiles smaller so you dont. This does not mean that your terrain objects have to be that small. For example, your tiles may only be 8x8 pixels, but your smallest terrain image .bmp may be 32x32 pixels, thus a terrain image covers a 4x4 tile area.

Now for objects that cover multiple tiles, the object is located in a center tile, and lets say for example that the object covers a 3x3 tile area, then the object is located in the center tile, and in the class for that object (or unit) for the movement function, there is a function that tells all 8 surrounding tiles that object is also in those tiles, so all 9 tiles will say that that object is in it. Or if an object is 2x2 tiles, then pick one of the 4 to be the main location, and then the movement function tells the other 3 tiles around it that it is there (or not there when it moves out of a tile).

Now, if you want true free movement, like say and object is located at (1029.9029,27.9291), then you do not use tiles at all for objects. You could still use tiles for terrain rendering, and thus each tile would be the size of the smallest terrain image you will be using. If your terrain images are 32x32 pixels, then your tiles will be 32x32. But objects will not be based on tiles. Tiles will never ever have anything at all to do with where an object is located. It would be just like in a 3D world, and object will be simply defined by a x,y,z float value in world space, but for a 2D game, it would be just an x,y float value, so in the ojbect class you would have:
float x_location;
float y_location;

So the object itself is the only place that stores its own location, its location is NOT stored in a tile. Then you have to use 3D collision detection but in 2-deminsions only.

And objects will also have a radius like:
float radius;
The radius value will signify how large the object is, and it can be used for either a circle or a square, if a square is used you may want to use the name ''size'' instead of ''radius'' and thus the area the object will take up would be size*size and squares would probably be faster for computational purposes, or you could use rectangles but then the object would need 2 float values. But dont store the radius or size value for each instance of the object, because ALL "Small Tanks" ect... will have the same ''size'' value.

To learn how to do this kind of collesion detection, there are plenty of articles for it on the GameDev web site, just convert them to 2D.

Possibility

to vasey:
no, no tile faq''s have included info on object collision which are bigger than a tile. One talked about how to display an object bigger than tile..but thats not what we are discussing here.

(i speak for my project and not dino''s as it only occured that we have same problem)

to possibility:
**thanks for the "possible" solution, but i have some real problems with your ideas concerning my tile-based design**

a) i dont think changing my map structure to accomidate the smallest movement possible is the way to go. What if some npc''s move 1 or 2 or 3 pixels at a time. Are tile points then really just a single pixel in size..Point is i dont want to limit movement based on how my tiles are structured. To add to this, extreme amounts of redundancy will also occur since almost all objects will now overlap many map tiles. My drawing routines become a nigtmare...at least my first thought of it does.

b) For a 2d game, adding objects to 3d space is Way, Way to much for me and this problem. I cant afford to go 3d calculations of objects in 3d space using some 2d/3d collision detection...are you insane..lol. Im sure if the ultima series can pull it off without 3d space, i can find a similar method.

So, basically your complete suggestion says for me to scrap my tile-based 2d design for some half-breed 3d object system... sorry, but thats not a solution for me, maybe for those 3d-Iso "Bracket" followers, but not for me.

Let me just say that i have spent about 3 hours searching over 50 of the probably 200 possible threads on collision detections posted on this website alone(i say 50 because more than 100 were about 3d collions of some sort). I found **1** that asked this same question in his thread, and none of the responses understood what he was asking and unfortunately changed the subject of the thread to a basic collision thread. 8(

I want to do this in a tile-based fashion using tile-based techniques. So for me, a 3D solution is overkill. Thanks for the suggestion though, maybe someone will find it interesting!

aka John M.
Never give up. Never surrender!

here's a simplified version of how I handled it before moving to to full 3d.

I had to seperate the graphical tile data and physical blocking data.

i.e. each map location stored whether or not it was "blocked"

objects when placed set the blocked value in one or more tiles,
I actually stored with each template object a bit array which contained the blocked tiles for that object and limitted tiles to a 16x16 blocking radius.

The only trick is the removal of objects, when unsetting a tiles "blocked" data you have to search max_radius tiles and make sure that no other tiles are blocking it. I did all this in the game editor, once in game the basic blocking data was static. In the game an object could not enter a tile if doing so would block any tiles that are already blocked.

It does depend on how your restricting movement. If things can only move from tile center to tile center this works well. They can move smoothly from one tile to another, but can only stop in tile increments. When an object moves, it has to check for valid move, then unblock any tiles its blocking, then immediately block an tiles it's moving to to prevent two objects from chosing to move into the same space.

So basically in game I store blocking information with the map.

my map tile struct looked something like this

maptile
{
int *Tiles
int Height;
char blocking;
}











Edited by - Thathmew on December 6, 2000 6:45:28 PM

quote: Original post by Dino
1) Every tile that the object covers has a pointer back to that object. So if object A covers 5 tiles, then all 5 tiles have pointers back to that object. Not a bad solution except keeping track of the object can be a pain when it moves.

I think this is the best method. I suppose you could supply
a larger grid than the actual tile size and use that for
collision rather than the actual tile grid. The way you
would choose the dimensions of the secondary grid would be
based on the average object sizes.

So if your tile was 32x16 and your average object size was
say 64x32 or whatever then you could choose this. That way you
wouldn''t be storing so many different pointers because your
least sized objects would probably all end up in one grid pos.
(Depending on placement that is)

When doing collision I just mapped the cords to this other grid
and did a further check.

I have used this method before but not in an Isometric sense but
the principles are the same.

Another side benefit of this would be in using this data for
the renderer as well. When rendering a tile you would now know
if an object/sprite was actually on the screen. Of course an object can span multiple tiles but you could set a flag against
the object when it has gone through the render phase.

So the speed you might lose on tracking the objects might well
be paid back to you when rendering them. When I actually implemented this I found that the real penalty was allocating
memory for the linked list and destroying it when objects moved
around. I basically built a cache pool of memory that I used to
allieviate this.

One method is to use multiple grids of different resolutions to perform collision detection.

Take the smallest object in your world. And then create a grid, call it G(0), covering your world, consisting of squares so that each square is just larger than this smallest object. Now create a series of additional grids, with each grid having squares exactly twice as large on each size as the grid before it, such that four squares of G(n) fit inside one square of G(n+1). And keep going until you have a grid with only one square covering your entire world.

Now for every object in your world, find the grid with the smallest square size such that the object can still fit within the square. So if G(0) has a square size of 1.5, then G(1) has a square size of 3.0 and G(2) has a square size of 6.0, and so on. So an object with a radius of .7 would go in G(0), an object of radius 1.4 would go in G(1) and an object with radius 10 would go in G(4).

Now for each object figure out the center of the object, and put a pointer to that object in the grid square in it''s grid that has it''s center. So if that object with radius .7 had coordinates for it center of (4.3, 7.4), it would go in G(0)[2, 4]. And if that object with radius 10 had coordinates for it''s center of (145, 63) it''s pointer would go in G(3)[6, 2].

To do actual collision detection, an object in a certain grid can only intersect objects with pointers in it''s square or adjacent squares. So the object in G(3)[6, 2] would have to do tests against all the objects in G(3)[7, 1], G(3)[7, 2], G(3)[7, 3], G(3)[6, 1], G(3)[6, 2], G(3)[6, 3], G(3)[5, 1], G(3)[5, 2], G(3)[5, 3]. But it also has to check if it collided with anything in larger than itself. Because each square in G(4) is twice the size of that in G(3) we only need to check G(4)[3,0], G(4)[3,1], G(4)[2,0], G(4)[2,1]. And all four of those are in G(5)[1,0] and G(6)[0,0] and G(7)[0,0] and so on until you''ve reached the grid with only one square. So it''s 9 squares in the grid that it lies in, 4 squares in the next grid, and 1 square for each grid after that.

If you do all the collision tests in your world at once, then you can stop here. You don''t need to test against the grids with the smaller square sizes because the smaller objects will do that test already.

If you want to test an individual object for any collisions it might have, you need to test against the smaller object grids as well. So you can use the center and size of the object to determine exactly which squares in the finer resolution grids to check. Continuing on the object with radius 10 and center at (145,63), let''s figure out the corners of the squares we need to check at G(0). So the upper right most point the object can be is (145 + 10, 63 + 10) = (155, 73), taking into account the max size of an object in G(0) we need to test for objects with centers all the way up to (155 + 1.5/2, 73 + 1.5/2) = (155.75, 73.75), so up to square G(0)[103, 49]. The lower bound is similarly (145 - 10 - 1.5/2, 63 - 10 - 1.5/2) = (134.25, 52.25) so square G(0)[89, 34].

Obviously you''d probably want to keep an index of the maximum grid that is actually being used, so you don''t keep checking against the world sized object continuously. (But you might want to keep that grid just in case you create a really big boom.)

Hmm Octree''s work on a similar principle for occlusion by breaking the problem down
further and further. Whilst it may not seem to be the topic I have read a technique
regarding voxel processing that might further help with collision. I will substitue
voxels for cells within a grid.

One way of keeping track of which objects are stored in which cell is simply to keep
a 3D array of cells in memory. Cell grids don''t have to be very large before this
become impractical. Sometimes it is convenient to store the grid at a variety of
different resolutions (spooky) this is done using an Octree.

The tree divides into eight branchs at every node. However if great depth is required
octree can also consume large amounts of memory.

If many of the cells are empty or the level of detail is known at the start, a table
of pointers can be used to represent the grid (Sparse array). Each location in the
table represents a group of neighbouring cells a linked list allows access to the
cells within the group.

Each cell within the group points to a list of objects to be found within that
particular cell.

The problem is how to make a good hash function that can be computed from the x,y and or
Z location of the object to be stored.

By using the x,y and/or z of the object then the address in the hash table can be
computed by combining the most significant few bits of each x,y and/or z. The table
contains a relatively small number of entries,each one representing a group of cells.

Objects with the same hash address are in fact near neighbours, which are in the same
group but not necessarly the same cell.

To compute the address of the (x,y and/or z) triple it is necessary to know the length
of the table and number of cells.

I have the algorithm here and may just see how this could be used for the purpose of
collision. The actually hash function is very,very fast.