Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (542) Games in Android Showcase (133) games submitted by our members Games in WIP (604) 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 4419 times) 0 Members and 1 Guest are viewing this topic.
theagentd

« JGO Bitwise Duke »

Medals: 366
Projects: 2
Exp: 8 years

 « 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.
Gudradain
 « Reply #1 - Posted 2012-01-07 18:16:18 »

Check in the Shared Code section. Someone already did something similar.
theagentd

« JGO Bitwise Duke »

Medals: 366
Projects: 2
Exp: 8 years

 « Reply #2 - Posted 2012-01-07 19:50:03 »

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

Myomyomyo.
 Games published by our own members! Check 'em out!
Orangy Tang

JGO Kernel

Medals: 56
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.

[ 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

« JGO Bitwise Duke »

Medals: 366
Projects: 2
Exp: 8 years

 « 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

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

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 Elsealabs (9 views) 2014-12-28 10:39:27 CopyableCougar4 (16 views) 2014-12-28 02:10:29 BurntPizza (20 views) 2014-12-27 22:38:51 Mr.CodeIt (13 views) 2014-12-27 04:03:04 TheDudeFromCI (18 views) 2014-12-27 02:14:49 Mr.CodeIt (25 views) 2014-12-23 03:34:11 rwatson462 (56 views) 2014-12-15 09:26:44 Mr.CodeIt (46 views) 2014-12-14 19:50:38 BurntPizza (93 views) 2014-12-09 22:41:13 BurntPizza (114 views) 2014-12-08 04:46:31
 Rayvolution 50x BurntPizza 30x basil_ 29x HeroesGraveDev 25x LiquidNitrogen 22x appel 18x kpars 18x Riven 15x KevinWorkman 15x princec 14x NegativeZero 13x pitbuller 13x gouessej 13x KudoDEV 12x kevglass 11x SHC 11x
 How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50
 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