Algorithms

Kevnar9-Nov-06 7:14

Kevnar

9-Nov-06 7:14

But what if it's 1.41, as is the case when going uphill diagonally? Does it still work?

"Go to, I’ll no more on’t; it hath made me mad." - Hamlet

ricecake9-Nov-06 7:21

ricecake

9-Nov-06 7:21

Yup, since the formulas are based on right triangles, and they can be computed totally in terms of the sides of the triangle. No scaling needed Smile | :)

One thing to watch out for is making sure your signs are consistent. For example, if you are going down from 7 to 6. In C and C++, there is the function atan2() which can take into account the signs of x and y for you, but I'm not sure if other languages provide it.

--
Marcus Kwok

Kevnar9-Nov-06 7:31

Kevnar

9-Nov-06 7:31

I'm just taking the absolute value of the difference, so going up or down is essentially the same result.

Thanks once again.

"Go to, I’ll no more on’t; it hath made me mad." - Hamlet

ejuanpp9-Nov-06 3:43

ejuanpp

9-Nov-06 3:43

If you have a grid of terrain heights you'll never meet the 90° case, so I considered a h threshold

cost = Sqrt(deltaX^2 + deltaY^2 + Math.Max(1, ((DeltaZ > h) ? 3 : DeltaZ))^2)

The case deltaX = +-deltaY = +-1 gives an angle of moreless 35°, I merged it with the case of 45°

I am assuming your grid is a "square" one and that you apply the formula when -1 <= deltaX, deltaY <= 1

Havent't check it though, hope it helps ...

Beginners question? Where does the exact double value go?

Kevnar9-Nov-06 4:13

Kevnar

9-Nov-06 4:13

Now that you mention it, a 90 degree angle would require infinite height in the adjacent terrain square.

I'm not sure what Math.Max does. You'll have to dumb that down to psuedo code for me.

My terrain is a square grid of heights from 0 to 255. I randomly assigned the values to each square and then smoothed them over with each square moving to the average height of its 8 neighbours. After a couple passes I got something that looks like a terrain. Then I assigned an arbitrary value for the sealevel and voila... a map.

Super clunky, but I'm too dumb to get into fractal terrain heights and all that. Actually, if I thought about it long enough, I suppose I could come up with something sort of fractalish, subdivide... displace... but I just wanted to get to the fun part, working out the Ai for the little people. Big Grin | :-D

"Go to, I’ll no more on’t; it hath made me mad." - Hamlet

ClockDivider8-Nov-06 6:48

ClockDivider

8-Nov-06 6:48

Hello, I have a strange problem, but probably it is because i am lacking knowledge, but what?

When debugging this:

double dTryThis = 1.23456789;

the debuggers variable watch shows this value for dTryThis:

1.234567889999999

instead of the expected 1.234567890000000! Confused | :confused:

And so is the wrong value used for further calculations! Is my computer sick or am I or what? I am on Visual Studio 2005 C++.

Thanks a lot for your help!

Martin...

Re: Beginners question? Where does the exact double value go?

Rob Graham8-Nov-06 7:09

Rob Graham

8-Nov-06 7:09

Floating point[^] numbers are represented as a fixed part (the mantissa) raised to an exponent. Both parts of the representation are necessarily binary numbers (i.e. every floating point number is the mantissa raised closest power of two ) As such, floating point numbers are always an approximation, with small values being closer together than large values (every time you increase the exponent, each bit in the mantissa becomes worth more).
What you are seeing is normal behavior for floating point numbers (double or single precision).
If you need a fixed precision, then you must use either integers (with a constant scaling factor),decimal[^] or currency, or some other exact numeric data type.

Re: Beginners question? Where does the exact double value go?

Dan Neely8-Nov-06 7:24

Dan Neely

8-Nov-06 7:24

Base10 numbers can't store all fractional values exactly without infinite repitition (1/3, 1/7, etc). Your computer uses base2 math internally and only converts to base10 for output. base2 can't store all numbers without repeating either. The thing you need to remember is that different bases have different sets of repeaters. In base3 1/3 is written as 0.1 (zero ones and one third), while in base10 1/3 is 0.3333333...... The base2/base10 one that causes the most confusion is 1/10 is a repeater in base2. You can work it out by hand if you want to see it with your own eyes. For financial transactions fixed point datatypes or types that store the number in a base10 format directly are typically used, but they have significant penalty over native base2 math. When precision identical to base10 hand work is not needed as long as it's good enough, native floating point types are used and a comparisons are made in a way that reflects the rounding issues. Instead of testinf equality by (f1-f2) == 0 you use Abs(f1-f2) < epsilon where epsilon is a delta smaller than your allowed error tollerance. If you're doing very extensive computations it's sometimes neccesary to order them in a way that minimizes total error, but normal applications generally don't need to worry about this.

for more detail see below. It's probably more detail than you need but is the best web reference I'm aware of.
http://docs.sun.com/source/806-3568/ncg_goldberg.html[^]

--
Rules of thumb should not be taken for the whole hand.

Re: Beginners question? Where does the exact double value go?

ClockDivider8-Nov-06 8:15

ClockDivider

8-Nov-06 8:15

Aaaah! Trying six hours on that issue, then waiting five minutes for your excellent answer! Thank you very much! Big Grin | :-D

Martin...

Scaling - help me

dharani7-Nov-06 0:06

dharani

7-Nov-06 0:06

Hi all
I have a problem with scaling a bitmap in different DPI situations .
The problem is : I have a dialog box where a bitmap is statically present . So during runtime without calling LoadBitmap () this bitmap is loaded into the dialog with the default size which is same you see in dialog editor . But problem comes when I change system DPI from 96 to 120.
Now the dialog and all the controls behind the bitmap are resized while the bitmap remains the same. I tried to implement StretchBlt () to scale the bitmap to new size - I do not succeed as I do not know how to map it to new DPI . To pictorise it ...

................. <---- The parent dialog
. .
. |---------| .
. | |<-- Bitmap with original static size when DPI=96
. | | .
. | | .
. | | .
. | | .
. | | .
. |---------| .
. .
.................

Now what I want is , when I change DPI to 120 then it should resize itself *from* the top,left of original size to the new sized bitmap .
After implementing StretchBlt as below ..I got it stretched fully to windows limits not as I want ...
pBitmap->LoadBitmap(IDB_BITMAP_ADDON_10_NOE);
POINT ptSize;
GetClientRect(hDlg,&rect);
pBitmap->GetObject(sizeof(BITMAP), &bitmap);
ptSize.x = bitmap.bmWidth;
ptSize.y = bitmap.bmHeight;
fxFactor = ((float)ptSize.x/(float)(rect.right-rect.left)),
fyFactor = ((float)ptSize.y/(float)(rect.bottom-rect.top));
xOffs = ((long)rect.Width()-(long)(ptSize.x/fxFactor))/2;
yOffs = ((long)rect.Height()-(long)(ptSize.y/fyFactor))/2;

dc->StretchBlt(xOffs,
yOffs,
(long)(ptSize.x/fxFactor),
(long)(ptSize.y/fyFactor),
&dcTemp,
0, 0,
ptSize.x,
ptSize.y,
SRCCOPY);

Now we have the real width,height of the bitmap + the windows dimensions . I need the bitmap to be scaled evenly to the new dimension of dialog keeping this bitmap in the center of the dialog . So I need to calculate the coordinates of the new bitmap with following points
1) Coordinates of the windows( = Center point of window)
2) Height,Width of bitmap
Can anyone please advise me ?

redindian

Re: Scaling - help me

Jörgen Sigvardsson7-Nov-06 13:02

Bresenhams algorithm for drawing lines

7-Nov-06 13:02

I think you're better off posting this in the MFC forum. I've seen people asking questions about rendering graphics there before with good results.

--
Larva-Tested, Pupa-Approved

Jörgen Sigvardsson6-Nov-06 12:59

6-Nov-06 12:59

So, I've been studying Bresenhams algorithm for drawing lines. I understand how it works, mainly because I've executed the algorithm on paper. The algorithm is quite beautiful.

However, I fail to understand why it works. Well, I kind of sort of understand, but it's more of a gut feeling than anything else. I have a book titled "Computer Graphics: Principles and Practice, Second Edition in C". It states that a line can be desribed as

1) F(x, y) = a*x + b*y + c = 0

It also says

2) dy = y1 - y0
dx = x1 - x1

and goes on to state that the slope intercept form can be written as:

3) y = dy/dx * x + B

It then concludes that

4) F(x, y) = dy * x - dx * y + B * dx = 0

I understand how 1), 2), 3) and 4) fit together. What I don't understand is where 1) comes from. I don't think I've ever seen an equation describing a line that way. I am unsure what it represents. I *think* it represents all values of x and y which are on the line. Is this the case? My gut feeling tells me that F(x, y) is a union of sorts of the functions f(y) and g(x), each describing the line from both axis. I would appreciate it if someone could help me understand this mystery of mine, or give me pointers to where I can find out.

--
LOADING...

Luc Pattyn6-Nov-06 13:43

Luc Pattyn

6-Nov-06 13:43

Hi,

ax+by+c=0 and y=dx+e are both formulas describing (all points belonging to) a straight line.
The former is fully symmetrical in x and y.

For both, you can introduce a new independent variable t, and then express both x and y as
a function of t, e.g.

x(t) = alpha * t + beta
y(t) = gamma * t + delta

this may make it easier to traverse the line: simply let t move from t0 to t1 (t0 and t1
corresponding to the known points (x0,y0) and (x1,y1).

Greetings,

Luc Pattyn

Jörgen Sigvardsson6-Nov-06 14:03

6-Nov-06 14:03

Heh. if ax + by + c = 0, then y = (ax + c) / b, right? Hum.. could it be that easy? Talk about not seeing the forrest for all the trees. D'Oh! | :doh:

--
Not Y3K Compliant

Bassam Abdul-Baki6-Nov-06 13:45

Bassam Abdul-Baki

6-Nov-06 13:45

y = ax + b ⇒ y = dx + e (change of letters) ⇒ y - dx - e = 0 ⇒ ax + by + c = 0. The last is the definition of any function in n variable (F(a₁, ..., a_n) = 0.

"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon

Web - Blog - RSS - Math - LinkedIn - BM

Jörgen Sigvardsson6-Nov-06 14:09

6-Nov-06 14:09

Yes. I think I saw too many trees, ran into a couple of them, got under one, and climbed one too many - so no, I didn't see the forrest. Big Grin | :-D

Thanks, both of you. I understand Bresenham's line algorithm now. Jig | [Dance]

--
Torn from tomorrow's headlines