Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Program Announcements / A waypoint utility

Author
Message
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 19th Mar 2010 04:19 Edited at: 19th Mar 2010 04:26
Link
NO! SCREEN SHOTS ARE POINTLESS FOR THIS.....

Here it is. There's an example of how to use it in the code.

The fastest code is the code never written.

Attachments

Login to view attachments
Back to top
Profile PM Email Website
T Frog
14
Years of Service
User Offline
Joined: 19th Mar 2010
Location:
Posted: 19th Mar 2010 17:12
Link
This is amazing!



Thanks so much, it helps a lot. I've been waiting for someone smarter than me to make something like this.

You rock dude.

Back to top
Profile PM
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 19th Mar 2010 23:48
Link
Yes, T Frog. I know you got lots of use out of that..... I would like to have someone that actually programs to comment.

Here's an update:

The fastest code is the code never written.

Attachments

Login to view attachments
Back to top
Profile PM Email Website
Dark Dragon
16
Years of Service
User Offline
Joined: 22nd Jun 2007
Location: In the ring, Kickin\' *donkeybutt*.
Posted: 9th Apr 2010 18:40
Link
Might try, thanks.

(\__/) HHAHAHAHAHAH!
(O.o ) / WORLD DOMINATION!!!!!!!!!!
(> < )
Back to top
Profile PM
Alfa x
17
Years of Service
User Offline
Joined: 1st Jul 2006
Location: Colombia
Posted: 12th Apr 2010 21:02
Link
Hawk,
Its very useful to make waypoint grid
For the shortest path, had you read swarm intelligence?
Back to top
Profile PM Email
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 12th Apr 2010 22:53
Link
I'm not sure what you mean by swarm intelligence.... Sounds cool though....

The fastest code is the code never written.
Back to top
Profile PM Email Website
Alfa x
17
Years of Service
User Offline
Joined: 1st Jul 2006
Location: Colombia
Posted: 13th Apr 2010 02:01
Link
Swarm Intelligence are the algorithms that take on base insects behavior to solve real life problems. One of the is the shortest path problem, another is to give AI to objects for example. (Is something in the same branch as Neural Networks)
Back to top
Profile PM Email
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 13th Apr 2010 15:39
Link
This method was based on routing accross a network. It was adapted to take into account the distance between the waypoints. I haven't put it to any practical use yet as I am not to that point in my current project, but I would like to see if someone has actually used it yet.

The fastest code is the code never written.
Back to top
Profile PM Email Website
veltro
User Banned
Posted: 20th Apr 2010 17:39
Link
Nice job.

Just a couple of suggestions:

Quote: "function AttachWaypointToWaypoint(WP1 as integer , WP2 as integer )
d# as float

d#=sqrt((WaypointLocation(WP1).x-WaypointLocation(WP2).x)^2+(WaypointLocation(WP1).y-WaypointLocation(WP2).y)^2+(WaypointLocation(WP1).z-WaypointLocation(WP2).z)^2)"


instead of

WaypointLocation(WP1).x-WaypointLocation(WP2).x)^2

use
(waypoint(WP1).x - waypoint(WP2).x) * (waypoint(WP1).x - waypoint(WP2).x)

or even better

dx = (waypoint(WP1).x - waypoint(WP2).x)

dx * dx


store the squared distance instead of distance (faster: you don't need to use sqrt)

If an application need the distance it can Sqrt it in a second time
Back to top
Profile
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 23rd Apr 2010 04:37
Link
I'm not sure you understand the point of the formula-- or maybe I don't understand your point. This formula is for 2-D distance (or the hypotinous of a triangle): D=sqrt(a^2+b^2). For the distance to be calculated properly, a square root of the sum of the squares of each side of the right triangle is needed.

For further explainations please look up 2-D distance formula in google or whatever. If that's not the point you were trying to make, then restate you question/observation.

The fastest code is the code never written.
Back to top
Profile PM Email Website
veltro
User Banned
Posted: 23rd Apr 2010 10:13
Link
I'll try to explain better.

I know that the correct formula for the distance is

D = sqrt(A^2 + B^2)

For a matter of speed, you can replace A^2 with A*A, cause CPU perform multiplication faster then power of, and A^2 = A*A. The same for B. So the formula can be written as

d = sqrt(A*A + B*B)

In your code A is waypointlocation(WP1).x - waypointlocation(WP2).x so A * A is
(waypointlocation(WP1).x - waypointlocation(WP2).x) * (waypointlocation(WP1).x - waypointlocation(WP2).x)

Again for a matter of speed you can store
(waypointlocation(WP1).x - waypointlocation(WP2).x) in a temporary variable, say deltax

deltax = (waypointlocation(WP1).x - waypointlocation(WP2).x)

and then

A * A = deltax * deltax

The same for B (y coordinate)

D = sqrt(deltax * deltax + deltay * deltay)

This way you got the right distance.
Again sqrt is a heavy operation in terms of CPU.
If you really need to know the distance as a number that is ok, if you need it for comparison, for example to find the shortest path, you can safely replace distnace with squared distance that is

SD = A * A + B * B

Given 2 ditance D1 and D2 and their squared distance SD1 and SD2 it is true that if D1 < D2 then also SD1 < SD2, if D1 =D2 then also SD1 = SD2, if D1 > D2 then also SD1 > SD2

i.e the comparison result does not change.

Hope this is clear.
Back to top
Profile
TheComet
16
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 23rd Apr 2010 12:03
Link
I also don't quite understand what you mean... I have another tip for a quick Pythagoras too:

veltro had a good point with A^2 It's much faster to use A*A.

My tip is to not use sqrt at all... Instead of:

c=sqrt(a*a + b*b)

You can use the original formula:

c*c = a*a + b*b

So if you want to check the distance, you multiply the distance with itself, and don't sqrt the result. Code-wise, instead of:



use:



Much faster.

TheComet

Back to top
Profile PM Email Website
veltro
User Banned
Posted: 23rd Apr 2010 15:18
Link
@TheComet

If you look carefully at the code you will see that the distance d is calculated as sqrt(a* a + b* b) and then stored in array Waypoint.

Then it is used to find the shortest path. What I suggest is to store not the distance but the squared distance.

Instead of storing sqrt(a * a + b * b) simply store a * a + b * b

The comparison result will not change and this way you avoid the heavy sqrt function.
Back to top
Profile
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 23rd Apr 2010 22:53
Link
Now I understand what you are saying... Sure, taking the square root is a little pointless just for background, but it's not like it will be used every frame. When an NPC/monster/alien needs to get to your location at Waypoint1, it finds the nearest waypoint to itself and goes to it. When it gets to that waypoint, it checks to see where to go next and then it doesn't check again until it gets to the next waypoint..... So, yea, you can just take the sqrt part out and it works just the same (and a smidge faster).

The fastest code is the code never written.
Back to top
Profile PM Email Website
TheComet
16
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 24th Apr 2010 12:52 Edited at: 24th Apr 2010 12:53
Link
@veltro

Ah, ok, I get it. Thanks for clarifying! That's what I tried to explain, but I didn't know you were on the same thing.

TheComet

Back to top
Profile PM Email Website
General Jackson
User Banned
Posted: 25th Apr 2010 06:33
Link
Thanks Hawk! My sister is always complaining about Screen Savers not being free, so I am writing her one.
I was going to code a wapoints but found this.

Back to top
Profile
Creating Game
15
Years of Service
User Offline
Joined: 21st Oct 2008
Location:
Posted: 27th Apr 2010 13:20
Link
Nice piece of software
Back to top
Profile PM
Hawkblood
14
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 30th Apr 2010 17:21
Link
Thanks for the comments.

The fastest code is the code never written.
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2024-04-18 11:17:34
Your offset time is: 2024-04-18 11:17:34