Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » overflowing int

This thread is locked; no one can reply to it. rss feed Print
overflowing int
David Sopala
Member #5,056
September 2004

I remember a lib back when that could handle bigger than your normal int can't remember what it was called though... and I am also unsure if it handles sqrt at all. I recently stumbled across a problem that would overflow an int then toss NaN back to my comparison which apparently is a large int forcing my function to always return true. So if someone could remind me of that lib or even a header I would appreciate it.

Edgar Reynaldo
Member #8,592
May 2007
avatar

If 2^64 - 1 is big enough for you, then use an unsigned long long int (commonly defined as uint64_t). sqrt operates on floats and doubles - cast to a double before calling sqrt and then back when you're done.

Otherwise, you need a big number library like GnuMultiPrecision (GMP) or Mike's Arbitrary Precision Library (MAPM).

torhu
Member #2,727
September 2002
avatar

What do you need such big numbers for? Maybe you could use a double, they've got much larger range.

Btw, there's no such thing as NaN for integers.

David Sopala
Member #5,056
September 2004

Lets say the player is at 100000 by 100000 that would be the circle. Now doing the math with squaring then square rooting I would get a NaN as feedback. Also I really only need int precision since I can't have something between pixles.

square a number add it to the square of another number then take a sqrt will never give a negative number. The max number I would have would be MAX_INT squared.

#SelectExpand
1bool Collision_Handler::Collision_Check(C_Circ *circ, C_Rect *rect) 2{ 3 int tar_x = circ->Get_X(); 4 int tar_y = circ->Get_Y(); 5 6 if(tar_x < rect->Get_X()) tar_x = rect->Get_X(); 7 if(tar_x > rect->Get_X() + rect->Get_SX()) tar_x = rect->Get_X() + rect->Get_SX(); 8 9 if(tar_y < rect->Get_Y()) tar_y = rect->Get_Y(); 10 if(tar_y > rect->Get_Y() + rect->Get_SY()) tar_y = rect->Get_Y() + rect->Get_SY(); 11 12 if(circ->Get_R() >= sqrt(((circ->Get_X()-tar_x)*(circ->Get_X()-tar_x)) + ((circ->Get_Y() - tar_y)*(circ->Get_Y() - tar_y))))return true; 13 else return false; 14 15}

Johan Halmén
Member #1,550
September 2001

#SelectExpand
1bool Collision_Handler::Collision_Check(C_Circ *circ, C_Rect *rect) 2{ 3 int tar_x = circ->Get_X(); 4 int tar_y = circ->Get_Y(); 5 6 if(tar_x < rect->Get_X()) 7 tar_x = rect->Get_X(); 8 if(tar_x > rect->Get_X() + rect->Get_SX()) 9 tar_x = rect->Get_X() + rect->Get_SX(); 10 if(tar_y < rect->Get_Y()) 11 tar_y = rect->Get_Y(); 12 if(tar_y > rect->Get_Y() + rect->Get_SY()) 13 tar_y = rect->Get_Y() + rect->Get_SY(); 14 15 if(circ->Get_R() >= 16 sqrt(((circ->Get_X() - tar_x)*(circ->Get_X() - tar_x)) + 17 ((circ->Get_Y() - tar_y)*(circ->Get_Y() - tar_y)))) 18 return true; 19 else 20 return false; 21}

...just wanted to be able to actually read the code.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Stas B.
Member #9,615
March 2008

Lets say the player is at 100000 by 100000 that would be the circle. Now doing the math with squaring then square rooting I would get a NaN as feedback. Also I really only need int precision since I can't have something between pixles.square a number add it to the square of another number then take a sqrt will never give a negative number. The max number I would have would be MAX_INT squared.

Having to use bignum arithmetic for game logic is pretty much a clear indication of a design flaw. Actually, your case is a perfect example of why logic and drawing shouldn't be mixed. Don't use pixels in your game logic. Use whatever units make the most sense for your game. It comes with the added bonus of smoother motion. :)

David Sopala
Member #5,056
September 2004

Who said anything about drawing? This is collision checking which I intend to be pixle perfect. Go figure it is in a collision_handler class guess that means draw_stuff_to_screen class somehow.

Stas B.
Member #9,615
March 2008

What on earth does collision detection between a circle and a rectangle have to do with pixels...? Why on earth do you use pixels as your game units?

David Sopala
Member #5,056
September 2004

Call them units then not that it matters. Your saying keep drawing and logic apart it doesn't really matter what kind of unit they are I would still have a grid MAX_int by MAX_int to get the most use out of it.

Stas B.
Member #9,615
March 2008

Look, if you need a bignum library for collision detection, you are very clearly doing something wrong. Trust me, there's probably not a single game that does that. If you tell us what exactly you're trying to achieve, we'll probably be able to suggest a simpler way of doing it that doesn't involve int overflows. :)

Arthur Kalliokoski
Second in Command
February 2005
avatar

If you run into overflow problems with normal ints, you'd eventually hit an overflow problem with huge ints as well. It's similar to the problem with cracks appearing in T-junctions in 3d meshes, doubles have fewer of them, but they still occur. The solution for that is to tesselate the T-junction into more triangles.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

David Sopala
Member #5,056
September 2004

Ideally a very large map. As you see I am using rectangles and circles to perform collision checking against. By a very large map I mean something like it will take you hours (litterally) to walk from one side to the other far side, but less if you are say driving a jeep or something... I probably shouldn't have used pixles as my explanation of unit, but when I am planning in my mind I can think in terms of something physical easier than some unit that is undefined. So basicly I want a very big map for players to walk around. As for buildings and other enterable structures - I am thinking I can make them on a far inaccessable side of the map and more or less "teleport" players into those areas. I say teleport only because I will use Set_Coords and it will basicly give them a sense of teleporting. So I need a map large enough to lets say have multiple buildings that one can enter and explore, probably a sewer system, and a few other places. I could in theory have multiple maps loaded on the server and swap them out with the player, my only fear there is as a player is loading into an area he dies. Maybe an immunity, but I could see players exploiting that. I might try the unsigned long long int to store the big number then sqrt it. My other option is to balance the equation a little more...

circ->Get_R() >= sqrt(((circ->Get_X()-tar_x)*(circ->Get_X()-tar_x)) + ((circ->Get_Y() - tar_y)*(circ->Get_Y() - tar_y)))
//Use this instead
abs((circ->Get_R()*circ->Get_R())-((circ->Get_X()-tar_x)*(circ->Get_X()-tar_x))) >= ((circ->Get_Y() - tar_y)*(circ->Get_Y() - tar_y)))

Stas B.
Member #9,615
March 2008

Quit thinking in terms of ints and pixels. Use meters as your units of measurement and floats to store them. It makes it much easier to reason about the dimensions of different objects, it's much more flexible and it avoids precision and overflow problems.

Let's suppose you want your map to take one hour to traverse on a fast jeep. How big should it be? If the jeep's speed is 100km\h, it's easy to tell that your map should be 100km wide. That's 100,000m. If your map is 100km by 100km, then the greatest possible distance between two objects would be sqrt(100000.0f * 100000.0f + 100000.0f * 100000.0f). You'll have no problems performing that calculation.

An important thing to note is that a proper engine will never check for collisions between objects so far apart. They obviously can't collide. You should at least divide your map into small rectangular regions (say, 20m by 20m) and only check for collisions between objects that are in the same region. Ideally, you'd implement quad trees for this kind of stuff.

For a complex game, you'll probably want to avoid having one giant map at all. There's no good reason to load it all into memory and process all of it when you can only see a small fraction of it at a time.

David Sopala
Member #5,056
September 2004

Server - client setup. Server "sees" the whole map at any given time. Though you are right about not checking something that reasonably won't be a collision. I only worry about something like a big dividing wall or a river etc that might be long in some places. Then again using multiple collision areas can fix that. I will add you would be absolutely right if it were a single player game as far as splitting it into smaller areas. So regardless I am stuck with a large map or linking maps together which I am unsure how to do it correctly for when you come to a seam in the world mobs need to cross the seams.

I did use that approach when writing a single player RPG that apparently no one here thought was good enough to offer any encouragement to finish everything from your graphics suck to it feels like a treadmill. Chuckle...

Stas B.
Member #9,615
March 2008

Giant objects are not a problem. The simply occupy more than one region.
[EDIT]
You seem to have edited your post while I was writing mine.
Even if you really must load and process the entire map, you should still divide it into logical regions and process only the ones that are visible by at least one player. Areas that are for the moment invisible by any player don't have to "freeze". You can keep processing them cheaply by using statistics instead of simulating each and every action of each and every object while nobody is seeing.

David Sopala
Member #5,056
September 2004

Ok maybe this will explain what I am thinking a bit. You have a wall kind of like the great wall of china. My collision rectangles are based off of coordinates and sizes now lets say we have a thin and skinny wall that is really long - lets say it is 10000 units(meters) long. Now lets say we only check to see if that wall's starting point is within 20 units(meters) so we walk down the wall for 25 meters turn towards the wall and walk through it.

Now maybe I can do some other math to see if I should do the math I already have.

not using my routines here just a quick psudocode kinda thing

if(rect_TLX <= player_x <= rect_BRX  and  rect_TLY <= player_y <= rect_BRY)

A slight tweak in there based on the collision circle's radius is also required.

Stas B.
Member #9,615
March 2008

I don't understand what you're talking about.
Here's what I was trying to suggest:

{"name":"rivert.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a657f236c17b6320451435567e3b699f.png","w":375,"h":347,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/6\/a657f236c17b6320451435567e3b699f"}rivert.png

Red player is inside a region that has a chunk of river in it. Check for collision with the river. Discover that the player is inside the river and push him out.

Green player is inside a region that has a chunk of river in it. Check for collision with the river. Discover that the player is outside the river and do nothing.

Blue player is inside an empty region. Do nothing.

David Sopala
Member #5,056
September 2004

say the river starts at 20,20 and goes untill 60,160 so thats 40x140 now your not populating an array since that is memory consuming and slow to check. I'm not sure how you intend to check parts of a rectangle when the rectangle is out of range.

Stas B.
Member #9,615
March 2008

You're making no sense. ???

Edgar Reynaldo
Member #8,592
May 2007
avatar

Stas is saying that you have to store the grid locations that the river occupies. Each grid location should have a list of objects that overlap it, and these objects should be checked for collision against each other.

As for your overflowing integer problem, there is no problem. Cast them to a float or a double, do your calculation, and then cast back to an integer.

verthex
Member #11,340
September 2009
avatar

Lidia might be able to handle square roots for large numbers.

#include <LiDIA/xbigfloat.h>
int main()
{
xbigfloat x;
sqrt(x,2,5);
cout << "Relative 5-approximation x to sqrt(2) = " << x << endl;
cout << "x as bigfloat "; x.print_as_bigfloat(); cout << endl;
return 0;
}

From the manual page 120.

Go to: