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.

AppGameKit Classic Chat / Free Code - Automatic waypoint system for use with AI systems

Author
Message
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 18:06 Edited at: 3rd Nov 2011 23:12
Link
This is a system I'm working on for a game but I thought I'd share it.

Latest Version!

It is not finished but is nearly there so I thought I'd share it and get some feedback. I just have to do a reverse search which will find a quicker route in some circumstances.

What does it do?
It allows you to create a set of waypoints either automatically or by inserting waypoints where you need them. Then you can use the "find_path" function to find the fastest route between any two points.

The fastest route is stored in an array which you can then read to get the route for your characters.

Currently the search takes less than 2ms on my machine so I'm thinking lag will be minimal.

Commands
init_waypoints:
This initialises some global variables. Some code still needs to be moved in here...

create_rect_obstacle(x#,y#,width#,height#,angle#)
Adds a rectangular obstacle (currently all obstacles are visible but I'll be adding a method to hide / show debug images later) and all the necessary waypoints needed to get around it from any angle

create_obstacle(x#,y#)
is a 'random' rectangle creator and the predecessor of the previous command, used for testing

add_waypoint(x#,y#)
Manually adds a waypoint into the system

calculate_waypoint_nodes()
Works out the closest 8 waypoints to every other waypoint and stores it (and the distance to it) as a 'node'. This data is used to calculate fastest routes later. Also any waypoints that clash with other scenery objects are deleted.

show_waypoints() / hide_waypoints()
This will be hidden in the debug code later

find_path(x1#,y1#,x2#,y2#)
This is the command used to calculate the fastest route between two points


If you plan on manually adding scenery it should be in physics group '2'...

Attached is the full code and a working test project.

I will be updating this source code as it improves.

Attachments

Login to view attachments
Back to top
Profile PM Email
Red Eye
16
Years of Service
User Offline
Joined: 15th Oct 2008
Location:
Posted: 4th Oct 2011 18:21
Link
Awesome!
Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 18:31
Link
Thanks @Red Eye

My advice is don't use it... yet.

It will be much more flexible / accurate and usable soon.

I tried it on 20 marines in my game and there was no noticeable lag, they just all set off on their own various routes to the rendevouz without pausing (except to shoot the odd zombie)...

Back to top
Profile PM Email
Red Eye
16
Years of Service
User Offline
Joined: 15th Oct 2008
Location:
Posted: 4th Oct 2011 18:37
Link
I tried the demo you included, and it works great.

I was thinking about making a platform AI bot. And use the same "make_obstacle" module. This means it would jump to the nearest obstacle (relative to you) if distance is close enough.
Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 18:45
Link
Quote: "I was thinking about making a platform AI bot. And use the same "make_obstacle" module. This means it would jump to the nearest obstacle (relative to you) if distance is close enough."

I hadn't considered using it for platforms, I have a feeling it would struggle for side scrolling games but I guess it could be adapted.

I made it for top down games really. I'm just tweaking the main path finding algorithm now to do an extra run to find a possible faster route, this is only necessary because the way the waypoints choose their nodes is not bi-directional so sometimes a faster route is missed looking from start to finish. My second run looks from finish to start and compares the minimum distance before deciding which route is best!

Back to top
Profile PM Email
BraindeaD
16
Years of Service
User Offline
Joined: 30th Mar 2008
Location:
Posted: 4th Oct 2011 19:08
Link
Thanks for sharing, baxslash.
maybe it will useful for me in my tanks game when cpu tanks are chasing the player. I'll follow this post to see the new versions.

Regards
Back to top
Profile PM
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 19:28
Link
Hi BraindeaD, I hope it will be useful! I'll be posting a new version over the next few days.

Tank games could certainly benefit from this kind of system.

Back to top
Profile PM Email
Scotty1973
AGK Backer
13
Years of Service
User Offline
Joined: 2nd Jun 2011
Location: Burton-on-Trent, uk
Posted: 4th Oct 2011 19:48
Link
Looks great!!! Can't wait to see the new version!

Scotty
Back to top
Profile PM
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 20:13
Link
Hey scotty! Burton on Trent! I'm in derby

Back to top
Profile PM Email
Cliff Mellangard 3DEGS
Developer
18
Years of Service
User Offline
Joined: 20th Feb 2006
Location: Sweden
Posted: 4th Oct 2011 20:35
Link
Nice work !

Maybe we should start putting all the good agk code snippets in the snippets board soon ?

The others simply write dbp or db for wath version of dark basic they use.
Why shouldt we simply write agk in front of our snippets in the same thread?
Back to top
Profile PM Website
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 21:00
Link
I don't see why not, this isn't quite ready yet though...

Back to top
Profile PM Email
bjadams
AGK Backer
16
Years of Service
User Offline
Joined: 29th Mar 2008
Location:
Posted: 4th Oct 2011 21:58
Link
idea: option to move in a bezier curve and not straight lines
Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 4th Oct 2011 22:07
Link
I'm sure that with a little extra work you could create a set of bezier curves from the positions of the sprites returned by the function. I don't really need it for my own game.

This code is a step or three along the road for any game that needs a pathfinding solution, nothing more.

Back to top
Profile PM Email
Hodgey
15
Years of Service
User Offline
Joined: 10th Oct 2009
Location: Australia
Posted: 5th Oct 2011 02:08 Edited at: 5th Oct 2011 13:58
Link
This is spectacular baxslash! Excellent work! Now all I've got to do is go through it in depth to see how you did it.

Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 5th Oct 2011 11:56 Edited at: 5th Oct 2011 11:57
Link
Thanks Hodgey! It's based on Dijkstra's Algorithm more or less but I kind of came up with my own way of doing it because I didn't really 'get' the code I found for the algorithm...

The pathfinding works like this:
Each waypoint has 'nodes' which are links to other waypoints. It stores the other waypoint's sprite number and the distance to it. Starting at the nearest waypoint to the start it loops through all the other waypoints that are attached to the first waypoint and finds the shortest distance to each of them (storing it in the waypoint array). Then it starts at the nearest waypoint to the target point and works back through the waypoints to via the shortest route (smallest stored value visible from each waypoint) until it reaches the start again.

There's a bit of optimisation after that but that's basically it!

There's also a bunch of code for automatically adding the waypoints and working out the nodes for each waypoint.

Back to top
Profile PM Email
Hodgey
15
Years of Service
User Offline
Joined: 10th Oct 2009
Location: Australia
Posted: 5th Oct 2011 14:14
Link
Ok, I think I understand. So if I had moving objects, I would need to call the find_path function each loop wouldn't I. I see this working out quite nicely baxslash, thanks for sharing!

Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 5th Oct 2011 14:19
Link
Quote: "So if I had moving objects, I would need to call the find_path function each loop wouldn't I"

No you could do what I am which is to store a set of waypoints in the character's array and then as he reaches a waypoint tell him to go to the next one, something like (psuedo code):


Back to top
Profile PM Email
baxslash
Valued Member
Bronze Codemaster
17
Years of Service
User Offline
Joined: 26th Dec 2006
Location: Duffield
Posted: 3rd Nov 2011 23:09
Link
This code is not quite 100% yet but it works in most cases. I'm posting the current version here as now I'm going to put it in my game. If I make any further adjustments I'll try to re-integrate them into this version and post it here (attached)!

Attachments

Login to view attachments
Back to top
Profile PM Email
Back to top

Login to post a reply

Server time is: 2024-11-22 09:08:30
Your offset time is: 2024-11-22 09:08:30