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.

Code Snippets / Strange pathfinder.

Author
Message
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 27th Jul 2004 05:36
Quite a fast (and strange) little pathfinding demo, check it out.



Van-B


Muhahahahaha.
Mattman
21
Years of Service
User Offline
Joined: 5th Jun 2003
Location: East Lansing
Posted: 27th Jul 2004 06:19 Edited at: 27th Jul 2004 06:19
Illegal image area at line 41

"Could you do something where you don't need a video card cause i don't have one" - Program Expert
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 27th Jul 2004 06:48
Oops! - forgot to say - run it at 800x600 minimum - needs a 512x512 image grab.


Van-B


Muhahahahaha.
Mattman
21
Years of Service
User Offline
Joined: 5th Jun 2003
Location: East Lansing
Posted: 27th Jul 2004 07:42
Pretty cool, pretty strange

"Could you do something where you don't need a video card cause i don't have one" - Program Expert
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 27th Jul 2004 08:24
I like the way it hugs the blobs, might make for some decent enemy AI.


Van-B


Muhahahahaha.
Lost in Thought
20
Years of Service
User Offline
Joined: 4th Feb 2004
Location: U.S.A. : Douglas, Georgia
Posted: 27th Jul 2004 11:07
cool run it at synce rate 10 or 20 to really see it choose its path.

Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 28th Jul 2004 12:24
grrr, whats with the "disable escapekey"?

its cool, yet very confusing. where's all the fancy pathfinding code? your whole source code looks like this:


"eureka" - Archimedes
genius
21
Years of Service
User Offline
Joined: 16th Oct 2003
Location: Utah, USA
Posted: 28th Jul 2004 12:34
Yeah PHAELAX, where is the code?

Why do they have BRAIL on Drive-Up ATM Machines?
Elthan
21
Years of Service
User Offline
Joined: 29th Jul 2003
Location: Spain
Posted: 9th Aug 2004 05:23
It´s really short. Could you explain it please? Thanks.
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 9th Aug 2004 08:38
Well, it's really a fancy flood fill. If you use a grid, and set your target to a flag on the grid - you can make multiple checks over the grid and look for non-flagged spaces with flagged spaces beside them. With the exception of the destination flag, it uses a direction flag which points to the path towards the destination, so:

`N=1, Ne=2, E=3, Se=4, S=5, Sw=6, W=7, Nw=8

If you check a blank grid location and it has a flag to the right of it, or East, you'd set the flag to 3, the code for East. Then you do this lots of times until your current grid location, your start position has a flag. When the start location has a flag it has a clear route to the destination, the simplest route, not the fastest though.

The code can be expanded on quite easily to calculate the quickest route, but I thought I'd keep it simple and let people mess around with it.


Van-B


Muhahahahaha.
Physics coder
20
Years of Service
User Offline
Joined: 25th May 2004
Location: United States
Posted: 9th Aug 2004 17:36
thats cool! could you comment it a bit cuz I don't understand how it works.

-----------------------------------
To delete the bug, delete the code.
Specs: Sony VAIO Laptop, Windows XP, P4 2.8Ghz, 512MB RAM, ATI Radeon 64MB video memory, DBP Upgrade 5.3.
Powersoft
21
Years of Service
User Offline
Joined: 1st Aug 2003
Location: United Kingdom
Posted: 13th Aug 2004 00:11
van is well known for uncommented source


Create or Play? You choose!
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 18th Aug 2004 20:43
Hehe, I get so many funny looks and humph?'s when I try to explain things here, there seems little point in commenting code, I'm clearly needing work on my writing . I've written 10 user manuals at work for my systems there, but nobody understands them either!.

I'll comment it this afternoon if I have time - while the boss is away . What though, is the most confusing part? - the array fill?, just so I know what to spend the most time on. Ohh! - I had a good idea for precalculated routes too, sorta like a shared brain for all your AI to get to key locations from anywhere using a precalculated route system. I'll explain it, and the quickest route idea - but won't code it for now, I'll be adding a full path finding system into my compo entry, which I'll be releasing the code for anyway.

Hopefully I'll get it nice and understandable, it's actually EUREKA! code, like when you have the bones of a little idea and it works far better than you expected.


Van-B


Muhahahahaha.
Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 19th Oct 2004 00:35
This is what im looking for , can you convert it so its usable for 3d ?

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 19th Oct 2004 00:59
You might not need to...

If you consider that the grid could be a terrain, or even a level - you only need to worry about 3D when you need more than 1 floor.

If you do need it totally 3D, then I'm not sure how I'd go about that - maybe a layered array, like set it as a 3D array - but I'd most likely use a point to point 3D system, which I'll have an example of at the end of the month (part of my compo entry you see). The 3D waypoint system is more for FPS games, the grid method is better for RPG's - so it really depends on what sort of game your planning.


Van-B


Muhahahahaha.
Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 19th Oct 2004 19:33
No it hase just one floor. This is the map:

ftp://imtec.afraid.org/map.jpg

And this will be the array map .. if im right :



But how do i use your code with objects. Im making a kind of UT game and i use functions for the player control and enemy control. Is it posible to write your code in one function for controlling an enemy? like uuuhm 'control_enemy(enemyobject,target)' so that the enemy moves with pathfinding to his target.

joep

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 19th Oct 2004 20:02
The pathfinder array would overlay the objects, like if theres an object inside a tile, the tile needs to be flagged as a collision. You would need an editor to let you specify which tiles are occupied.

As for actually tracing the path - all you really need to do is check the tile the enemy is standing on, then move in the relevant direction. If the enemy strays from the set path, it'd find it's way back onto it again because of the way it works. I'd suggest having a few key locations and calculating paths for those - like the player start location, that way if you spawned you could set all your enemies to go after the player if you liked.

First thing you should look into is getting a little map editor/collision editor - then you can start calculating paths that you can easily check.


Van-B


Muhahahahaha.
Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 19th Oct 2004 20:42
Quote: "then move in the relevant direction."


How do i do that? just with point and move object?

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 19th Oct 2004 21:22
Nah, the way this pathfinder works is with numbered direction flags...

N=1, Ne=2, E=3, Se=4, S=5, Sw=6, W=7, Nw=8

So if the flag your character is standing on is 1 - you need to move north. You could simply make a speedX# and speedZ# array, like:

DIM spdx#(8)
DIM spdz#(8)

d=0 : spdx#(d)=0 : spdz#(d)=0
d=1 : spdx#(d)=0 : spdz#(d)=-1
d=2 : spdx#(d)=1 : spdz#(d)=-1
d=3 : spdx#(d)=1 : spdz#(d)=0
d=4 : spdx#(d)=1 : spdz#(d)=1
d=5 : spdx#(d)=0 : spdz#(d)=1
d=6 : spdx#(d)=-1 : spdz#(d)=1
d=7 : spdx#(d)=-1 : spdz#(d)=0
d=8 : spdx#(d)=-1 : spdz#(d)=-1

Then you'd adjust the position depending on the spdx# and spdz# for the tile your standing on. This is untested remember - I can't remember if those values match what's in the code.


Van-B


Muhahahahaha.
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 19th Oct 2004 21:24
LOL! - it already does that, just looked over the code.

If you multiply node_movex() and node_movez() by the relevant speed, you should be able to use the little moving example, just need to make it into a function that can get the real world positions of a specified object and move it to suit.


Van-B


Muhahahahaha.
Wiggett
21
Years of Service
User Offline
Joined: 31st May 2003
Location: Australia
Posted: 19th Oct 2004 21:54 Edited at: 19th Oct 2004 21:56
argh zippy red line, went so fast was har dto tell if it avoided the whiteys at all. also whats with disabling the escape key, had to alt f4 outta it . havent read your explanation, but i skimme dover something saying array, i take it you just put up an array of where it could and couldnt go, could it be easily transferred to 3d by makign the same array but placing 3d objects instead of dots?

oops just read the last four posts and got an answer. so yeah basically just setting up a tile array and placing your level by tiles could make it work.

Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 19th Oct 2004 22:10
Yup - if you want to watch it, set the frame rate to 10. You'll notice that it's not exactly the results you'd expect, but it'd certainly be fine for an RPG, it goes for the simplest route so diagonals are used a lot, but that gives it a nice curvey path rather than clinical accuracy so it's no biggie - nothing wrong with a little chaos in your code.


Van-B


Muhahahahaha.
Wiggett
21
Years of Service
User Offline
Joined: 31st May 2003
Location: Australia
Posted: 19th Oct 2004 22:52
except when it's the wierd games workshop take on chaos with half naked women with deformities dancing with knives and super marines that have had growths form to give them two heads or some other horrible deformities.

Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 20th Oct 2004 02:55
Quote: " if the flag your character is standing on is 1 .."


Ok i know that But how do i get the right flag? how do i know which way he must go.. sorry i dont really get it

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 20th Oct 2004 03:06
Well, you see this bit of code...


chk_d=safe_node(chk_x,chk_z)
if chk_d>0 and chk_d<10
chk_x=chk_x+node_movex(chk_d)
chk_z=chk_z+node_movez(chk_d)
else
gosub random_dest
endif

What that does is find out which tile your standing on, then sets that to chk_d, then it moves the chk_x and chk_z depending on the direction. The direction X and Z movements are stored in node_movex and node_movey - passing the direction number to those arrays will return the speeds. You'd divide your object position by the tile scale in your game, like if you have the scale at 100x100 DB units per tile - you'd then divide the X and Z positions by 100.


Van-B


Muhahahahaha.
Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 20th Oct 2004 19:45 Edited at: 20th Oct 2004 19:55
yay! I think i got it

check this:



It takes a while before you see something, because he creates a lot of boxes..

thanks Van-B

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 20th Oct 2004 20:35
No worries, glad your on top of it .


Van-B


Muhahahahaha.
TEH_CODERER
21
Years of Service
User Offline
Joined: 12th Nov 2003
Location: Right behind you!
Posted: 23rd Oct 2004 06:27
Nice one Jopie dopie.

Realms Of Tutopia: Rise Of Evil
http://www.freewebs.com/elbsoftware/index.htm
Turoid
21
Years of Service
User Offline
Joined: 1st Nov 2003
Location: The Netherlands
Posted: 23rd Oct 2004 07:48
thanks, it's van's code though..

Do you need a complete FPS,3rdPS engine ?? Or a collision command libary?? well here it is:
http://forum.thegamecreators.com/?m=forum_view&t=38869&b=6&p=0
Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 25th Nov 2004 04:08
Ahh, well I think the problem is that it's trying to grab a 512x512 image, so in DBC you should set the display mode to 800x600 - it should be peachy after that.


Van-B


It's c**p being the only coder in the village.
Shadow Robert
22
Years of Service
User Offline
Joined: 22nd Sep 2002
Location: Hertfordshire, England
Posted: 25th Nov 2004 12:07
i had to put it at sync 30 just to see what it was doing, damn fast lil bugger.

this could come in very useful, i was just thinking about how to do path finding. Need to include that in my current AI routines, just wonder how I can do it in 3D; Suppose it would need to tie in with my area evaluation raycasts for that entity..

i'll just add it as part of my learning algorithm and run it a few times to get it intelligent enough i think.

thanks!


Van B
Moderator
22
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 26th Nov 2004 00:02
I think the best way to utilise it would be to have an extra dimension on the data array, so you could have a few different paths, then add the option to calculate everything, not just until there's a path.

If you calculated everything, and the path to go to the player position, you'd only need to calculate it once, then set the enemies onto the right path. Really, it's quite a powerful little thing - if you set some key areas for your enemies, and calculated the paths for them, you could get to any key location from anywhere on the map at anytime and without causing any strain on the processor at all . The demo calculates a different path once it gets to it's location, and calculating the path is the slow bit.

I mentioned this before, but it's also possible to get it following the shortest path. Right now it keeps going till it gets a clear path to it's destination - so the first path that it finds might not be the shortest, just the simplest. For example, moving 10 spaces diagonally is equivalent to moving 20 spaces straight, so if it can use diagonals it will, simply because diagonals feed the pathfinding system quicker than straight paths.

I should have done a bigger example, but I thought I'd release it as is and let people experiment with it to suit themselves.


Van-B


It's c**p being the only coder in the village.

Login to post a reply

Server time is: 2024-11-23 16:56:12
Your offset time is: 2024-11-23 16:56:12