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.

Dark GDK / the wieghted node algoritm path finding

Author
Message
3d point in space
9
Years of Service
User Offline
Joined: 30th Jun 2009
Location: Idaho
Posted: 5th Aug 2012 20:37 Edited at: 5th Aug 2012 21:28
This is an path finding algorithm that I did a while back that was not A*, I currently use A* but this algorithm make more logical sense. The algorithm I demonstrated to high school kids because they didn't understand A*. This is more like the weighted node path finding algorithm. Basically this algorithm you make a vector that list that finds the path by following walls. Using the left hand rule that if you put you hand on a wall of a maze you will eventually find the end, but I also but weights on places already visited so it is less likely that it will choose the same node twice. This is a good algorithm if it is a maze like structure game. With not very many open spaces that the can be visited. So I used different collars of tiles to show the progress of the algorithm being solved. A* is still the best algorithm hands down.
Notes press enter to view progress of the node






Developer of Space Chips, pianobasic, zipzapzoom, and vet pinball apps. Developed the tiled map engine seen on the showcase. Veteran for the military.

Attachments

Login to view attachments
haliop
10
Years of Service
User Offline
Joined: 2nd Sep 2008
Location:
Posted: 6th Aug 2012 13:44 Edited at: 6th Aug 2012 13:48
very cool indeed
i didnot know that vector can be used like this

vector<vector<int>> myvector;

edit
can you explain a bit about how to use such a vector?



[URL] http://forum.thegamecreators.com/?m=forum_view&t=198467&b=22 [/URL]
3d point in space
9
Years of Service
User Offline
Joined: 30th Jun 2009
Location: Idaho
Posted: 7th Aug 2012 06:12 Edited at: 7th Aug 2012 06:27
Vector<vector<int>> makes a 2 dimensional vector that you can add on or subtract so. The maze can basically be any size it wants to be vector<vector<int>> will make the array as following.
v

vectortemp.pushback(int);
Then the vector has one row. Know use vectortemp[0].pushback(int); inserts a column. Sorry about my typing using a droid. I tested A* and this methee on a maze and superizingly it performed just as well as a* on an maze on adverage.

Developer of Space Chips, pianobasic, zipzapzoom, and vet pinball apps. Developed the tiled map engine seen on the showcase. Veteran for the military.
haliop
10
Years of Service
User Offline
Joined: 2nd Sep 2008
Location:
Posted: 7th Aug 2012 14:59
aha i see , nice , learned something new ty.



[URL] http://forum.thegamecreators.com/?m=forum_view&t=198467&b=22 [/URL]
Wana7262
7
Years of Service
User Offline
Joined: 23rd Nov 2011
Location:
Posted: 11th Aug 2012 08:59
how to use this? can I use it in my FPS game?
3d point in space
9
Years of Service
User Offline
Joined: 30th Jun 2009
Location: Idaho
Posted: 13th Aug 2012 02:50 Edited at: 13th Aug 2012 02:52
i thought no one wanted to use it. I guess you can use it, not that hard of an algorithm to implement. So Implementing it is a-lot easier then a* algorithm, and its different. I don't know if your game if it has a-lot of walls and maze like structure then sure use it. It will be just as fast as A* in maze like structures.

Developer of Space Chips, pianobasic, zipzapzoom, and vet pinball apps. Developed the tiled map engine seen on the showcase. Veteran for the military.
haliop
10
Years of Service
User Offline
Joined: 2nd Sep 2008
Location:
Posted: 13th Aug 2012 11:54
i would use it but i cant seem to understand it so..

i use a much easier method where i declare the points an Ai can move rather then searching i agree it is less dynamic more like a static navagation system but it seams to do the right job , the only thing is that i have to declare each step :/

Login to post a reply

Server time is: 2019-05-24 17:25:47
Your offset time is: 2019-05-24 17:25:47