Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (757)
Games in Android Showcase (229)
games submitted by our members
Games in WIP (844)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Visibility graph pathfinding  (Read 7465 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2012-01-07 18:07:14 »

After making a small implementation of Dijkstra's algorithm to solve my pathfinding needs, I realized how unfit it was to pathfind on a grid when my units could move in any direction. Since I don't seem to manage to implement a decent tie-breaker to make my tile paths more straight and natural compared to how a unit moves, I decided to try out a visibility graph approach. I simply decide on a few waypoints (the convex corners of walls) and compute the visibility between them. The code was pretty simple, but I have some severe problems going forward now, but let's start with the pros:

 - Perfect paths. Units can actually just walk between the nodes generated with no need to post-process the tile path generated by Dijkstra's, which may result in an suboptimal path when the unit moves even though the tile path is optimal (since units don't walk in only 8 directions).
 - Simple and possibly much more efficient pathfinding, since long distances can be quickly traversed with a single link.

 - THIS:

 - 175.000 links for a single 128x128 tile map with very few walls. I can optimize this by removing some unnecessary links to approximately half (or maybe even less) lines.
 - The pre-computing of the lines is dead slow, taking more than a second. Since I pretty much have to recompute the entire visibility map every time a node changes (which they do all the time), this is simply put impossible. The above mentioned algorithm improvement will increase the computation time even more.
 - The main problem is that I need to do n^2 visibility checks on the waypoints since I can't set a maximum distance (large rooms would be untraversable).
 - How do I add links to the start and goal positions? Doing 175.000 raycasts for both the start and goal positions isn't exactly real-time, and there is no other solution that I can think of.

It gives me a lot better paths, but it is dead slow, so what can I do? Dijkstra's is a lot faster, but gives me pretty terrible paths. In most cases I can post-process the path to an identical path as a visibility graph would give me, but in some cases the unit might take a huge detour around an obstacle unless I do an unhealthy number of raycasts in the post-processing which seems to be my only solution at the moment.

I really did like visibility graphs, since they produce so nice results, but they are pretty much limited to very small maps due to both the cost of eventual dynamic generation and more importantly memory usage. Oh, well, I guess I just have to improve my path post-processing...

TLDR: This turned into a rant about visibility graphs being unusable for large maps due to memory consumption and insanely long pre-processing time.

Offline Gudradain
« Reply #1 - Posted 2012-01-07 18:16:18 »

Check in the Shared Code section. Someone already did something similar.
Offline theagentd
« Reply #2 - Posted 2012-01-07 19:50:03 »

I remember that, but that was for arbitrary polygons. I have tiles...

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

« Reply #3 - Posted 2012-01-07 19:59:17 »

Waypoint based pathfinding is pretty sucky for 3d worlds IMHO. I'd suggest pre-processing your tile map into larger 'walkable' rectangles of adjacent tiles, then making a graph from adjacent rectangles and running A* over this walkability graph.

[ - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline SimonH
« Reply #4 - Posted 2012-01-07 20:43:25 »

Waypoint based pathfinding is pretty sucky for 3d worlds IMHO.
I'm inclined to disagree - I've used a combination of waypoints and local fuzzy navigation to very good effect. Hand placed waypoints work best, but programatically putting a waypoint close to every convex corner also works quite well.

Since I pretty much have to recompute the entire visibility map every time a node changes (which they do all the time)
Not sure what you mean by this - do you mean that the map's geometry is constantly changing?

People make games and games make people
Offline theagentd
« Reply #5 - Posted 2012-01-07 22:31:32 »

Since I pretty much have to recompute the entire visibility map every time a node changes (which they do all the time)
Not sure what you mean by this - do you mean that the map's geometry is constantly changing?

Not constantly, but very often.

Offline t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

Google App Engine Rocks!

« Reply #6 - Posted 2012-01-28 02:21:37 »

if A goes to B. Draw straight line between A and B. If that line intersects an object, split the line at C and move C until A-C and C-B miss original object (move C normal to line A-B). Recurse on A-C route and C-B route. I think this might only work for concave objects.

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Offline Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

« Reply #7 - Posted 2012-05-11 18:51:41 »

Also consider using a quad tree for this. So you look in very large grids and only look in more detail if the grid has an obstacle in it. In this way you only need to get into very fine detail in a few instances, so it can greatly reduce your comparison count.

See my work:
OTC Software
Offline krasse
« Reply #8 - Posted 2012-05-11 18:59:41 »

You could use the old grid approach but smooth it out during execution by periodically doing raycasts towards the node following the current next node.

It will make the path shorter if possible during the path following phase.

There are also some other methods for optimizing bad paths, but I have only tested this method with good results (not on a grid though).

Pages: [1]
  ignore  |  Print  

EgonOlsen (60 views)
2018-06-10 19:43:48

EgonOlsen (42 views)
2018-06-10 19:43:44

EgonOlsen (61 views)
2018-06-10 19:43:20

DesertCoockie (241 views)
2018-05-13 18:23:11

nelsongames (142 views)
2018-04-24 18:15:36

nelsongames (141 views)
2018-04-24 18:14:32

ivj94 (883 views)
2018-03-24 14:47:39

ivj94 (144 views)
2018-03-24 14:46:31

ivj94 (795 views)
2018-03-24 14:43:53

Solater (159 views)
2018-03-17 05:04:08
Java Gaming Resources
by philfrei
2017-12-05 19:38:37

Java Gaming Resources
by philfrei
2017-12-05 19:37:39

Java Gaming Resources
by philfrei
2017-12-05 19:36:10

Java Gaming Resources
by philfrei
2017-12-05 19:33:10

List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!