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 / Smooth path finding!

Author
Message
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 24th Apr 2003 15:03
Link
This is just something I was playing with.
If you do path finding you will get the path, but it will be very edgy. That's why I made this smooth pathfinder. It first find the path the normal way, but then makes it smooth. It takes a much longer time to load, but I made it so that the routine can only use 2 ms per frame on thinking about the path. It will take longer this way, but you will keep a steady framerate. This would be like AI that is thinking for a second }:> . It works pretty good now, although it does cut off some edges. However that can be fixed with sliding collision.

You should try it out, tell me what you think. And if you find any use for it, please let me know.

Kevil
Back to top
Profile PM Email
pugmartin
21
Years of Service
User Offline
Joined: 3rd Jan 2003
Location: United Kingdom
Posted: 24th Apr 2003 15:37
Link
Very cool. Might use this. Good work!!

That picture actually is me you know...
Can anyone post me a banana?
Back to top
Profile PM Email Website
hexGEAR
22
Years of Service
User Offline
Joined: 3rd Nov 2002
Location: Naytonia
Posted: 24th Apr 2003 16:53
Link
thats pretty good!

everyday of life is a new chapter that has already been fortold but is up to the soul to capture.
Back to top
Profile PM Email Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 25th Apr 2003 00:34
Link
Weird! It sometimes looks like it's taken a wrong path, but the A* path is correct. I think it's the smoothing of the path that can result in a longer path. It actually makes it look more like AI - that is, not every decision is perfect.

Nice one!

Thanks in advance.
All the Best,
StevieVee
Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 25th Apr 2003 00:56
Link
Well, I do think that the smooth path always make the path shorter. Firstly, the path is calculated using the A-star method. Then the smoothing starts. It is based on the A-star path, but if it can take a linear path that can skip a few steps of the A-star path, it will. That's how it works. It shouldn't make the path longer.
Maybe you could enlighten us with a screenshot???

Kevil

Back to top
Profile PM Email
Red general
22
Years of Service
User Offline
Joined: 19th Nov 2002
Location: United Kingdom
Posted: 25th Apr 2003 11:49
Link
What is this A* method, and does it work with dbc?

My computer melts regulary - perhaps it likes being fondue
Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 25th Apr 2003 13:43
Link
uhm, this is made in DBC, with the A* method, so yes it works .

Kevil

Back to top
Profile PM Email
matt rochon
21
Years of Service
User Offline
Joined: 15th Mar 2003
Location: Canada
Posted: 25th Apr 2003 19:19 Edited at: 25th Apr 2003 19:40
Link
hey i tried doing this not too long ago and failed miserably, that is the path worked but was sooooo wickid slow that it wasnt useable

this is sweet and i would like to use it if thats ok with you

EDIT: any ideas on how to make the target a moving target?
Back to top
Profile PM
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 25th Apr 2003 20:03
Link
Hmmm, a moving target would be very hard. Mainly because it takes quite long to calculate such a smooth path. It can however load while playing the game. The problem is that during the calculation the starting point and the target point will be moved. That would make it very difficult, but maybe I will try. I'll let you know if I got it to work.

Kevil

Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 25th Apr 2003 20:45
Link
This is a method that works ok I guess. After a certain amount of walking he rethinks his route and continues on the new route. And that without a framedrop. You should definately try this out. Your mouse is the target. You can move it around as you like, and the path will follow you. Although you shouldn't go over blue squares, because then it will stop working.

BTW, if you want to use it, you may. If you need any help with it, you should contact me.

Kevil

Back to top
Profile PM Email
Kohai of UWDesign
22
Years of Service
User Offline
Joined: 12th Sep 2002
Location: France
Posted: 25th Apr 2003 22:57
Link
Great piece of work Kevil ...


( saves the sources quickly, for a later use ! )

[Kohai]
[url]www.underwaredesign.com[/url] [url]www.kohaistyle.com[/url]
pIII 733/256 Ram/Geforce 256
Back to top
Profile PM Email Website
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 26th Apr 2003 01:38
Link
Quote: "Maybe you could enlighten us with a screenshot??? "


This one could have taken the straighter path, it makes no difference to the A* calculation, but for the curved path it looks like a longer route was taken. I like it, it's still correct but it looks more random.



Thanks in advance.
All the Best,
StevieVee
Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 26th Apr 2003 02:14
Link
Now I see. Well, it's because of the smoothing code. In this case a keypoint was created below the block. That's why he is going round it. At that point it doesn't know yet it could've gone straight. The only way to do this is to recheck at the end which keypoints can be removed. But since that would require more calculation I left it out.

Kevil

Back to top
Profile PM Email
matt rochon
21
Years of Service
User Offline
Joined: 15th Mar 2003
Location: Canada
Posted: 26th Apr 2003 19:12 Edited at: 26th Apr 2003 19:17
Link
hmm im having trouble getting it to rethink the path when my player (or target) is moving around

think you could help me out?

EDIT: i only need it to work on a 9*9 grid not a 32*32 grid, will that speed it up alot?
Back to top
Profile PM
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 26th Apr 2003 20:46
Link
I could try to help you out. What exactly is the problem? Or if you send me your code, I could help you better .

Kevil

Back to top
Profile PM Email
matt rochon
21
Years of Service
User Offline
Joined: 15th Mar 2003
Location: Canada
Posted: 27th Apr 2003 03:25
Link
well i have 30 or so monsters in my level, which is block based so a* works well

prob is i dont know how to take apart your code to make it only find the next 1-2 values and re calculate in, say, 2 seconds
Back to top
Profile PM
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 27th Apr 2003 13:34
Link
Hmm, with 30 monsters that would be pretty slow. But if it is on a 9x9 grid that would speed it up a bit. The problem is that they can't calculate their path at the same time. So you have to do it after each other. But then it has to be pretty fast. I can't really explain you how to do this. Maybe you send me code?

Kevil

Back to top
Profile PM Email
matt rochon
21
Years of Service
User Offline
Joined: 15th Mar 2003
Location: Canada
Posted: 27th Apr 2003 20:43
Link
ok, just to let you know theres never 30 monsters being calculated at a time

theres 30 monsters throughout the whole level, which is pretty big

the most id need to calculets is probly about 4-5 at a time

check the source for my code
Back to top
Profile PM
BatVink
Moderator
21
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 27th Apr 2003 21:33
Link
You could calculate a different monster each cycle. So for 5 monsters, for example, each would continue on the same path for 5 cycles, then recalculate. I'm sure that wouldn't cause too many problems.

Thanks in advance.
All the Best,
StevieVee
Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 27th Apr 2003 21:55
Link
You will need a big array which contains the points for each monster. So that the points# array contains points for each monster(you will probably have to store how many points are used). If you do it like this, you can't reset the points# array like I do. Then you need a variable for the current monster. You calculate the path for this monster. Therefor you only have to define the start and end point for this monster and then let him do the calculation. After you're done with this calculation, you increase the variable to go to the next monster (or you calculate which monster you want to calculate next, like the closest one).
Every monster that's not being calculated at that point needs to move following the points he has calculated. He must do this until he's the next one to be calculated. Then he must follow the new path etc.
The code that moves the object (in my demo the code that draws the dots) need to be done separately and constantly. That's the big difference with my demo you should have to make. It's not easy, but it's possible.

Kevil

Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 27th Apr 2003 23:47
Link
Like this!

I put the pathfinding in a function, so you can use it easier.

Kevil

Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 28th Apr 2003 00:04
Link
This one is better (small change).

Kevil

Back to top
Profile PM Email
kevil
21
Years of Service
User Offline
Joined: 24th Nov 2002
Location: Netherlands
Posted: 28th Apr 2003 00:10 Edited at: 28th Apr 2003 13:31
Link
Ok, last version

EDIT: Forget this one. It has issues.

Kevil

Back to top
Profile PM Email
Back to top

Login to post a reply

Server time is: 2024-11-24 04:50:38
Your offset time is: 2024-11-24 04:50:38