Notification

Icon
Error

All Forums Inbox Search

Options
Go to last post Go to first unread
DavidJCobb
DavidJCobb

Rank: Peasant

Posts: 923

Thanks: 303 times
Was thanked: 221 time(s) in 180 post(s)

Medals:
Beta Forum Participant: Beta Forum ParticipantCreator: You can earn this medal by uploading levels and discussing your level in the forums.

#1 Posted: Sunday, April 13, 2014 4:45:10 AM(UTC)
I just created a waypoint graph algorithm that you can use for pathing. Here's a video of the test demo in action. You can see me ordering characters to locations; they walk to the nearest part of the waypoint graph, and then follow the graph to go where they need to go.

What is a waypoint graph?
A waypoint graph is something like a roadmap. It tells characters where they can go, and how they can get there without running into obstacles. If they follow the lines of the graph (this is called "pathfinding" or just "pathing"), they should arrive at their destination safely.

When Koding enemies and NPCs, you may notice that they just don't know how to avoid obstacles. They'll run right into terrain or props, with no clue how to go around them. They need a pathfinding system, and a waypoint graph is just that.


An image of a waypoint graph; each "node" on the graph is a sphere, and nodes are connected with lines. Characters that use the graph will try to stick to its nodes and lines, avoiding the unpainted terrain.


You can use waypoint graphs for lots of things. Perhaps you need villagers to wander around a town intelligently; the built-in Path object won't very well for wandering, but a waypoint graph will let you define all possible routes and paths a villager could take, and the algorithm will pick the shortest of those for any given situation. Maybe you need enemies to be able to navigate through hallways and quickly reach a target; a waypoint graph will keep them from blindly running into the walls.

Sounds great, but... what's the catch?
Waypoint graphs are an old technique, and they have some limitations. They can't account for dynamic obstacles, such as movable crates, that might be pushed in a character's way. They also don't handle wide open spaces very well; there, you'll see zig-zaggy movement. However, they're probably the best navigation technique we'll get in Project Spark unless Team Dakota gives us some sort of pathing mesh system.

These limitations are somewhat easy to avoid. For example, you can avoid using waypoint graphs in clearings and meadows, and save them for town roads and the hallways of buildings. You probably can't avoid that whole "movable crate" issue, but you wouldn't really be able to using Project Spark's built-in movement anyway.

So where do I go to check this thing out and use it?
You can find the world here.

The demo allows you to order around two characters, Red and Blue, and shows you the waypoint graph nodes that they're following to reach their destinations. You can press A to see all nodes on those characters' graph, or press B to get a view of three squirrels that randomly wander around on a separate waypoint graph.

There is a signpost in-game. Move your cursor under it to see instructions on how to use the waypoint graph algorithm in your own map. (I've also included them in a spoiler here.)

Technical details


I built this in a few hours, so there's almost certainly some issue I haven't discovered. Please do message me with bug reports. I am most likely to respond if contacted over Xbox LIVE (DavidJCobb) or reddit (/u/davidjcobb).

Edited by user Sunday, April 13, 2014 8:06:31 PM(UTC)  | Reason: Updated thread to match v1.1 info.

DavidJCobb
DavidJCobb

Rank: Peasant

Posts: 923

Thanks: 303 times
Was thanked: 221 time(s) in 180 post(s)

Medals:
Beta Forum Participant: Beta Forum ParticipantCreator: You can earn this medal by uploading levels and discussing your level in the forums.

#2 Posted: Sunday, April 13, 2014 8:16:08 AM(UTC)
In my currently sleep-deprived state, I only just realized that importing this whole system into a level might not be the most straightforward process. I want this to be as easy to use as possible, so here's a narrated video tutorial that shows exactly how to copy the waypoint graph system into another level.

[EDIT] With tonight's v1.1 update, it's now easier than ever to put this system in a level. When playing the demo level, move your cursor over the signposts from left to right for full documentation, including instructions on building a waypoint graph. Some of the information in the video is still relevant, so I'll leave it up for viewing. [/EDIT]

If you, dear reader, take this waypoint graph system and use it in a project, please do let me know! I'd love to take a peek at what it's used for when I get time. :)

Edited by user Sunday, April 13, 2014 8:07:55 PM(UTC)  | Reason: Updated thread to match v1.1 info.

Zer0fluX
Zer0fluX

Rank: Desert Sparrow

Posts: 389

Thanks: 115 times
Was thanked: 145 time(s) in 112 post(s)

Medals:
Beta Forum Participant: Beta Forum ParticipantCreator: You can earn this medal by uploading levels and discussing your level in the forums.

#3 Posted: Sunday, April 13, 2014 9:44:48 AM(UTC)
This is very cool! Nice work!

As a side note, it seems I'm not the only one creating personal libraries of common gaming/game development functions for Project Spark. When I first started I jumped into making my Boogie Lights game. Since that experience (which was mostly positive), I've been making tools and reusable components.
Mac x Dino
Mac x Dino

Rank: Brin Fish

Posts: 63

Thanks: 8 times
Was thanked: 10 time(s) in 10 post(s)

Medals:
Beta Forum Participant: Beta Forum Participant

#4 Posted: Tuesday, August 12, 2014 1:58:26 AM(UTC)
Hey,

I just wanted to let you know, that I used your waypoint graph algorithm in my level: A Pile of Gold

thanks for sharing it...
EinherjarLucian
EinherjarLucian

Rank: Brin Fish

Posts: 41

Thanks: 20 times
Was thanked: 5 time(s) in 3 post(s)

Medals:
Original Spark: Alpha ParticipantBeta Forum Participant: Beta Forum Participant

#5 Posted: Thursday, August 28, 2014 11:10:49 AM(UTC)
This level doesn't seem to want to load... is there a newer version?
DankerPie3
DankerPie3

Rank: Peasant

Posts: 807

Thanks: 30 times
Was thanked: 208 time(s) in 182 post(s)

Medals:
Beta Forum Participant: Beta Forum Participant

#6 Posted: Wednesday, October 22, 2014 11:30:01 PM(UTC)
Hey David,

Re. problem with Waypoint Graph.

This is a nice piece of work that I adapted sometime ago in a world broken by hippo, I went back to consider repairing the old broken world and noticed that it is not working as it used to and it is not my customization as it has the same problems in your shared world.

I haven't investigated intently, but the cause of the problems is most likely the changes to the character's animated 'slow down' as they reach their destination. In essence the characters run and slow down before every node looking daft.
As a quick fix I ramped up the distance that the character must reach from its destination node before it is 'deleted' to 3m instead of the 1m. Now the character doesn't have time to slow in my test world before moving on to the next node, however, this means it will 'cut corners' more dramatically.

In a simple 'linear' path, this is probably going to be OK since you can put nodes in walls, etc. knowing the character will turn before them, but in a multi-node grid, you will not be able to have nodes in walls and props!

I haven't had enough time to know if sufficient advanced movement property changes will negate this slow down effect or if it is a hard wired animation we cannot overide, which is what I suspect, but thought you and other users should know.

Thanks though, because I think it will work for me in my context with the quick fix.
Back to top
Forum Jump  
You cannot post new topics in this forum.
You cannot reply to topics in this forum.
You cannot delete your posts in this forum.
You cannot edit your posts in this forum.
You cannot create polls in this forum.
You cannot vote in polls in this forum.


This page was generated in 2.215 seconds.