|
My new project, I'm working on some path-finding algorithms for little AI
people. I have a grid of terrain heights and I have a pathing algorithm. The
trouble I'm having is how to weight the movement cost from one square to the
next. If moving across level terrain from one square to another is 1, how do
I cost uphill and downhill travel? I'm kinda stumped.
Also, moving diagonally is technically 1.41 in distance, should I cost it as such or just leave it as one for simplicity's sake? What are the pros and cons?
Any thoughts?
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
I think you should leave it as 1.41, otherwise you'll have funny results 
Regarding height, maybe a cost formula like sqrt(deltaX^2 + deltaY^2 + (k*deltaZ)^2) might do
You could change the k coeff if climbing is more or less expensive than moving horizontally.
|
|
|
|
|
Wow. It never occured to me that the Pythagoreum thing worked in three dimensions. Thanks. That helps a lot.
My question is though, what to change the value of k to? If the target square is n higher or n lower, how do you cost it for the expense of climbing uphill, or downhill as compared to walking over level ground? I thought about giving it an arbitrary value based on the difference in terrain heights, but that seemed kinda clunky to me.
What I should do I suppose is find a chart on the internet of the amount of calories burned in walking as opposed to stair-climbing and wall-climbing. That might help.
Thanks again.
----------------------
...ten minutes later
Okay, I looked up the calorie charts and it turns out that stair-climbing is approximately double straight walking, and wall-climbing is approximate triple straight walking. So if I convert that to angles:
0 = 1
45 = 2
90 = 3
Now how do I convert that into a formula so that values in between return their appropriate costs?
I'll assume the values are the same for going down in terrain as well, though they might be slightly cheaper.
-- modified at 9:13 Thursday 9th November, 2006
cost = 1 + (angle / 45)
d'uh. I better get some coffee. Thanks all.
-- modified at 9:27 Thursday 9th November, 2006
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
I felt curious about the calories issue, i think it is a good idea of giving values to k I've found this link:
http://www.calorie-count.com/calories/activities/17.html
Regards
|
|
|
|
|
I figured it out. Thanks, kind sir.
k = 1 + (angle / 45)
Now to figure out how to calculate the angles... 
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Just remember your trig functions:
/|
h / |
/ | o
/ |
/ θ |
------
aI remember them with the mnemonic SOHCAHTOA:
SOH -> sin(θ ) = opposite / hypotenuse
CAH -> cos(θ ) = adjacent / hypotenuse
TOA -> tan(θ ) = opposite / adjacent
Then, to find the angle, you can use the inverse trig functions:
θ = asin(opposite / hypotenuse) = acos(adjacent / hypotenuse) = atan(opposite / adjacent)
In standard Cartesian coordinates, if the triangle is oriented as above with the origin located where θ is, then the adjacent side (a) is x, and the opposite side (o) is y. So, since you usually know x and y, there is no need to calculate the hypotenuse to find the angle, since you can then do θ = atan(y/x).
Be aware that the above identities are true only for radian angles. If you need degrees, then you must convert at the end using the identity 180 degrees = π (should be a pi, but it looks funny in my font) radians.
--
Marcus Kwok
|
|
|
|
|
I kinda wish I took Trig. I suck.
Thanks anyway.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Maybe the first part of this might help:
Trigonometry[^] at MathWorld.
Some of the stuff towards the bottom gets into some advanced stuff, but at the bottom of the page there are a bunch of links that you could follow that might help too.
--
Marcus Kwok
|
|
|
|
|
Okay. I think I got this...
So in this case, x would always be 1 (or 1.41 if it's diagonal), and y would be the difference of the current terrain height and the target terrain height?
No wait. That's not right. I'll have to figure out the ratio of x (being 1) to y (being anywhere from 0 to 255).
It sucks being almost a nerd, but not quite.
-----------------------------------------------
K... I went with an arbitrary ratio of 25:1. So if the difference is 255, that'll count as 10x (approximately). Hopefully that works.
Thanks all.
-- modified at 11:45 Thursday 9th November, 2006
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
I'm not quite sure what you mean... From your other post, I think the way you have your terrain is basically a matrix of heights (just random numbers I picked):
+---+---+---+---+
| 3 | 2 | 2 | 1 |
+---+---+---+---+
| 5 | 6 | 7 | 8 |
+---+---+---+---+
| 6 | 9 | 9 | 7 |
+---+---+---+---+
| 4 | 6 | 5 | 4 |
+---+---+---+---+ Say, you wanted to find the angle between the '6' cell and the '7' cell in the middle of the matrix. If you think about like you're looking at the matrix from the side (as if you were actually looking at the terrain, but more like a cross-section), then the second row would look like:
---
---/ 8
---/ 7
---/ 6
5Assuming that the distance between cells (not counting diagonally) is 1 (as you said, for diagonally it should be sqrt(2)=1.414). So, if we just look at the 6 and 7 levels ("zoomed in"):
-----
/ 7
/
-----/
6we can make the triangle:
-----
/| 7
/ |
-----/--+
6So, I think you do want the difference in the terrain heights as your y.
--
Marcus Kwok
|
|
|
|
|
Yup. That's what I figured as well.
The question was, if the distance between 6 to 7 is 1, and the difference in heights is anywhere from 0 to 255, what ratio do I use to scale down 0 to 255 to corespond with the distance of 1 grid square. I went with 25:1 (arbitrarily).
Thanks for your help.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Well, I don't think you need to scale the y values to calculate θ...
Examples:
x=1, y=1:
θ = atan(1/1) = atan(1) = π / 4 = 45 degrees
x=1, y=255 (a very tall slope):
&theta: = atan(255/1) = atan(255) = 1.566 = 89.775 degrees (almost a vertical wall, which makes sense if you are going from a square at height 0 to a square at height 255.
--
Marcus Kwok
|
|
|
|
|
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
|
|
|
|
|
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
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
|
|
|
|
|
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
|
|
|
|
|
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 ...
|
|
|
|
|
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. 
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
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! 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...
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
Aaaah! Trying six hours on that issue, then waiting five minutes for your excellent answer! Thank you very much! Martin...
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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...
|
|
|
|
|
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
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
