Sign in to follow this  
Jiia

Negative cell coordinates

Recommended Posts

Jiia    592
This is not really game related, and it's not very math entisive, so I thought this might be the best place to ask. I've just recently starting working with negative cells. In all of my previous projects, coordinates were always positive in cells. Now they can be negative. I'm wondering what other programmers would do to get the proper cell coordinates? It's a pretty dumb question, I know. But I've only been able to come up with a hacked method to translate the proper locations:
int cell_x = position_x / cell_space;
int cell_y = position_y / cell_space;
if( position_x < 0 )
  cell_x--;
if( position_y < 0 )
  cell_y--;
This is because x position -1 through -31 with 32x32 cells should exist in x cell -1. And int -31 / 32 == 0. Perhaps there is a better way to compute the cell locations so that the sign of the position coordinates make no difference? No hurry, just looking for advice. Thanks.

Share this post


Link to post
Share on other sites
Mastaba    761
Actually, don't you mean -32 to -1 should be mapped to -1 for a cell size 32 units wide? Well, anway, the problem you have discovered is the integer rounding behavior. To change the behavior you need to either use that "hack" or use the floating point unit to do the integer divide while having the floating point unit set to round down mode.


#include <stdio.h>
#include <float.h>

int main(int argc, char* argv[])
{
int position=-1;
int cell_size=31; // example
int result;

// set rounding mode to round down (you should set this back to its
// normal setting when you no longer need rounding down)
_controlfp(_RC_DOWN, _MCW_RC );
_asm
{
fild position;
fidiv cell_size;
fistp result;
}

printf("%i/%i=%i\r\n",position,cell_size,result);
return 0;
}



Share this post


Link to post
Share on other sites
xEricx    572
Sorry if that's not the kind of answer you're looking for, but, why must your cells have negatives coordinates?

I mean, if you REALLY want to have negative coordinates, have you thought of using unsigned coordinates and substract an offset?

If want your tiles to go from [-32,32] then your offset would be "-32"

This way you get tiles from 0 to 64, and applying your -32 offset results in -32 to 32 coordinates, and you remove the conditionnals.

Hope this helps

Eric

Share this post


Link to post
Share on other sites
Jiia    592
Pretty interesting answers!

The world space is infinite to whatever degree. So it would be difficult to use an offset, if I understand correctly.

Maps are made up of seperated grids. Each grid is 2048 inches in width and height, and contains 32x32 cells (cells are actually 64x64 points; I only used 32x32 to simplify). So the map itself is like a grid, using these grids as cells. I can build onto maps by just editing a certain grid. Locations that have been modified are saved to file with only their grid coordinates as identification (WorldMap_005x008.map). They are then loaded on the fly as the player moves around. A default location exists to represent blank, unedited areas. So maps can just go on and on, or at least until math stops functioning. It also makes it really easy to expand maps.

Quote:
Original post by Mastaba
Actually, don't you mean -32 to -1 should be mapped to -1 for a cell size 32 units wide?

If the cell is 32 points wide, a positive coordinate would only be in cell zero up until the 31.999inf mark. As soon as it crosses over to 32, it moves into cell +1. In negative coordinates, a world coordinate of something like -0.000001 would be cell location -1 (as soon as it's not zero). Or at least that's my reasoning. So any negative amount more than -32 would be cell location -1, but I think -32 is in cell -2. Is that incorrect? Perhaps I'm confusing myself. Or maybe I threw you off by saying -1 to -31 instead of 0 to -31?

I appreciate the suggestions.

Share this post


Link to post
Share on other sites
smart_idiot    1298
I'm fairly sure this worked at some point in time.


#ifndef AUTO_ARRAY_HPP
#define AUTO_ARRAY_HPP

/** \file autoarray.hpp
\brief Home of the AutoArray class.

\see AutoArray
*/


#include <deque>

/** \brief AutoArray is an automatically resizing array class, basically a wrapper for deque.
\param T The type of element to index.

It allows you to access any index, and, should it not exist, it will be created.
The size of the array includes the lowest accessed index, to the highest accessed index.
Negative indicies are allowed.
*/


template <typename T> class AutoArray
{
protected:
typedef std::deque<T> container_type; ///< The internal container type we're using to store the array in.

public:
typedef typename container_type::value_type value_type; ///< The type of values the array stores.
typedef typename container_type::pointer pointer; ///< A pointer to a value.
typedef typename container_type::reference reference; ///< A reference to a value.
typedef typename container_type::const_reference const_reference; ///< A constant reference to a value.
typedef typename container_type::size_type size_type; ///< An unsigned integer type.
typedef typename container_type::difference_type difference_type; ///< A signed integer type.
typedef typename container_type::iterator iterator; ///< An iterator that can change values.
typedef typename container_type::const_iterator const_iterator; ///< An iterator that can't change values.

protected:
container_type elements; ///< A container for the elements we're storing.
difference_type base; ///< The first valid index, the first element in elements is this index in the AutoArray.
value_type default_object; ///< The default object to use should an element not exist.

public:
/** \brief AutoArray constructor.
\param def The default object to use when a requested element doesn't exist.

Creates a new, empty array.
*/


AutoArray(const_reference def = value_type()): base(0), default_object(def)
{}

iterator begin() /// Returns an iterator to the first valid element, note however that this may not be index 0.
{
return elements.begin();
}

iterator end() /// Returns an iterator to the last valid element.
{
return elements.end();
}

const_iterator begin() const /// Returns a constant iterator to the first valid element, note however that this may not be index 0.
{
return elements.begin();
}

const_iterator end() const /// Returns a constant_iterator to the last valid element.
{
return elements.end();
}

bool empty() const /// Returns true if the array contains no elements.
{
return elements.empty();
}

void clear() /// Removes all elements from the array.
{
elements.clear();
base = 0;
}

difference_type first_index() const /// Returns the first valid index.
{
return base;
}

size_type size() const /// Returns the number of valid elements the array contains.
{
return elements.size();
}

bool valid(difference_type index) const /// Returns true if \a index can be used to get an existant object.
{
return index >= base && static_cast<typename container_type::size_type>(index-base) < elements.size();
}

/** \brief A constant reference to an index.
\param index The index to the requested value.

Returns the requested element if it exist, otherwise a reference to the default object.
*/


const_reference operator [] (difference_type index) const
{
if(!valid(index))
return default_object;

return elements[index - base];
}

/** \brief A reference to an index.
\param index The index to the requested value.

Returns the requested element if it exist, otherwise resizes the array to make it valid and returns the requested element.
*/


reference operator [] (difference_type index)
{
if(valid(index))
return elements[index - base];
else
{
if(elements.empty())
{
base = index;
elements.resize(1, default_object);
return elements.front();
}
else if(index < base)
{
elements.insert(elements.begin(), base-index, default_object);
base = index;
return elements.front();
}
else
{
elements.resize(index-base+1, default_object);
return elements.back();
}
}
}
};

#endif




Feel free to run it through doxygen for the documentation.

Share this post


Link to post
Share on other sites
xEricx    572
Then, are all your tiles fixed width?

You could simply "index" each tile from ]-inf, inf[ and then multiply this index by your width / height to know the exact positionning of a tile.

so if your width / height is 32, a tile located at 3,-2 would be from:

x left posX * width
to
x right (posX+ 1) * width - 1
y top (posY + 1) * height - 1
to
y bottom posY * width

this sample tile should be, with 3,-2, from 96 to 127 and -33 to -64

which seems to be correct.

Testing with a "boundary value" such as 0, 0 gives us 0 to 31 and 0 to 31, which seems correct too.

The problem with that solution is that if you have variable width / height, you'll have to store indexes based on this width / height, which doesn't make much sense but would still work.

Also, I don't know how you're editing your map, but you might as well save directly the world position of a tile when you edit it, inside the tile itself? This removes the calculation at runtime and gives you perfect results with fixed / variable tiles.

Hope I was helpful, good luck with your project :)

Share this post


Link to post
Share on other sites
Jiia    592
Quote:
Original post by xEricx
Also, I don't know how you're editing your map, but you might as well save directly the world position of a tile when you edit it, inside the tile itself? This removes the calculation at runtime and gives you perfect results with fixed / variable tiles.

Hope I was helpful, good luck with your project :)

Extremely helpful. My "tiles" are fixed width, but they aren't really tiles. They actually represent nothing at all. Just space. The grids are sort of tiles. Just a large polygonal terrain area. Terrain areas do keep record of their coordinates. The cells in a terrain area grid are the size of a quad in the terrain, but there's no physical object to represent them.

The cells will be used to contain area-checks with a large amount of objects and a large amount of space. For example, ray intersects test against the grid cells before computing terrain heights or collisions with other objects. Basically, the ray intersects the 2D grid, then world objects which are resting in the cells that were overlapped with the ray are checked for polygon intersects. The objects don't hold any sort of record for their cell locations. They could belong to several cells at once if they are large. They just check their range of cell coordinates against the ray-intersected cells, then do polygon level stuff if they match.

The point where the objects check their range of cells (like 2,0 to 4,2 or such, meaning an object resting on a 2x2 area) is where I have my hack. They divide their coordinates and subtract half of their width / height.

Sorry, didn't really mean to rant again. Thanks [smile]

Share this post


Link to post
Share on other sites
Mastaba    761
I'm still not certain you understand fully correctly. I drew a nice diagram to explain things more clearly.



The solid end of the cell segment is included, the hollow end of the cell segment is excluded. Now do you see why -32 is part of cell -1?

Share this post


Link to post
Share on other sites
Jiia    592
Quote:
Original post by Mastaba
I'm still not certain you understand fully correctly. I drew a nice diagram to explain things more clearly.

Definitely correct. Thanks for going to such lengths to point that out, I can be pretty stubborn. Guess I need to rework my code a bit.

It means my hack doesn't work correctly. It would have to be something like..
int cell_x = position_x / cell_space;
if( position_x < 0 && -cell_x % 32 )
cell_x--;
What a mess.

Share this post


Link to post
Share on other sites
Zahlman    1682
Exploiting 2s-complement arithmetic:


// ~x == (-x) - 1
// thus this maps -32..-1 into 31..0, etc.
// that means the division result will be 0 when it needs to be mapped to -1,
// 1 for -2, etc. But we know how to do that mapping ;)
int cell_x = (position_x < 0) ?
~(~position_x / cell_space) : position_x / cell_space;

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this