Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (753) Games in Android Showcase (228) games submitted by our members Games in WIP (842) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Visibility graph pathfinding  (Read 7315 times) 0 Members and 1 Guest are viewing this topic.
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.

Cons:
- 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.

Myomyomyo.
 « Reply #1 - Posted 2012-01-07 18:16:18 »

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

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

Myomyomyo.
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

 « 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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
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
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.

Myomyomyo.
t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

 « 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.
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
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

 nelsongames (5 views) 2018-04-24 18:15:36 nelsongames (5 views) 2018-04-24 18:14:32 ivj94 (586 views) 2018-03-24 14:47:39 ivj94 (49 views) 2018-03-24 14:46:31 ivj94 (383 views) 2018-03-24 14:43:53 Solater (63 views) 2018-03-17 05:04:08 nelsongames (110 views) 2018-03-05 17:56:34 Gornova (159 views) 2018-03-02 22:15:33 buddyBro (704 views) 2018-02-28 16:59:18 buddyBro (93 views) 2018-02-28 16:45:17
 KaiHH 13x Zemlaynin 10x SHC 10x ByerN 10x NuclearPixels 10x Guerra2442 6x Damocles 6x VaTTeRGeR 5x ags1 4x Spasi 4x orangepascal 4x philfrei 4x mesterh 3x princec 3x ndnwarrior15 3x DrZoidberg 2x
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org 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‑gaming.org