Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (538)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (600)
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  
  A* Multiple paths to goal  (Read 875 times)
0 Members and 1 Guest are viewing this topic.
Offline roland
« Posted 2014-06-24 00:13:33 »

Hey,
I have a problem with my pathfinding for bots - they will only choose the shortest path. I however do not want to use Dijkstra's due to the amount of possible paths in the map being too large. (I'm searching from one side of the map to the other).

Here's my example image, start point on the left, goal on the right. Blue are walls / unwalkable.


Right now the bots will take this path only:


I want the bots to choose all "intelligent" routes to the goal, eg. take the shortest path along any possible route.
Here's some examples:













I added some more tiles to show bad paths - There's no point for bots to do this, humans wouldn't.





Can you guys give me any ideas on how I could do this? I need to somehow determine options for routes, then I can make each bot choose one at random when they spawn.

I was thinking of having a list of paths from the bot's position to the goal. Firstly I add the shortest path,
then having a loop, finding paths that have to be "different" from the paths that are currently in the list. I would do this by checking the number of nodes that are the same in the current path to any of the paths already in the list. So at least X nodes have to be different in each path. Once I can't find a path that has X nodes different, I'll stop. But I don't know how I can cut out the "stupid" paths where they go around in circles or something, because some stupid paths can be shorter than the longer routes. Will Dijkstra's be required for this? It needs to be fast enough to calculate for each bot multiple times in their life (eg. if they get knocked off their path then they will have to find a new one)

Thanks,
roland
Online moogie

JGO Ninja


Medals: 15
Projects: 6
Exp: 10 years


Java games rock!


« Reply #1 - Posted 2014-06-24 01:12:28 »

Maybe I am getting confused, but there is only one shortest path for the images you have provided. Do you want instead to have multiple semi-optimal paths?

Java4k RIP 2014
Offline micecd

Senior Newbie





« Reply #2 - Posted 2014-06-24 01:52:48 »

Solution, use 2 paths and then combine them.

Split up the 2 points A -> B into A -> B -> C

Pick a point on the grid from random points between 0-width for x and 0-height for y for walkable points.

Then, apply the pathfinding for AB then the pathfinding for BC, and then combine the path points.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline JVallius
« Reply #3 - Posted 2014-06-24 06:50:38 »

Hey, interesting problem!

I thought something like this:



A1...B4 are waypoints. First, place waypoints like showing in the picture. Calculate the first path from Start to A1, A2 or A3. From there, calculate a path to B1, B2, B3 or B4, and from there to the End.

You can place waypoints manually or code a simple loop.

Hope this helps.  Smiley

Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #4 - Posted 2014-06-24 08:07:17 »

Here's an idea:

Rather than passable/impassable for your tiles, have a 'cost' associated with moving through them. Impassable are +infinity, and initially all passable tiles start with cost 0. Then:

1. Find the most optimal path considering the costs with regular A*
2. Store that path as a possible path
3. For every tile that the path touches, increase the cost of traversing that tile.
4. Repeat until you have 'enough' paths.

This effectively means that every path after than the first, it's 'harder' to take the same route as an existing path. Note that you don't set the tiles to impassable, as you still want the tiles to be used if there's no other option (like the tile immediately right of your green start square).

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline JVallius
« Reply #5 - Posted 2014-06-24 09:38:29 »

@Orangy Tang

This sounds good, much better than mine!

Offline roland
« Reply #6 - Posted 2014-06-24 12:25:44 »

Thanks for your comments Smiley

Maybe I am getting confused, but there is only one shortest path for the images you have provided. Do you want instead to have multiple semi-optimal paths?
Yeah exactly.

Hey, interesting problem!

I thought something like this:



A1...B4 are waypoints. First, place waypoints like showing in the picture. Calculate the first path from Start to A1, A2 or A3. From there, calculate a path to B1, B2, B3 or B4, and from there to the End.

You can place waypoints manually or code a simple loop.

Hope this helps.  Smiley
I like this idea - I didn't think of that. Although I'd have to figure out how to place the waypoints on my maps, which are quite more complex than this - I need a solution for any possible map made and this might be difficult.

Here's an idea:

Rather than passable/impassable for your tiles, have a 'cost' associated with moving through them. Impassable are +infinity, and initially all passable tiles start with cost 0. Then:

1. Find the most optimal path considering the costs with regular A*
2. Store that path as a possible path
3. For every tile that the path touches, increase the cost of traversing that tile.
4. Repeat until you have 'enough' paths.

This effectively means that every path after than the first, it's 'harder' to take the same route as an existing path. Note that you don't set the tiles to impassable, as you still want the tiles to be used if there's no other option (like the tile immediately right of your green start square).

Cool. I think I'll try this. Some routes are much "taller" than 1 tile as in my example map so I'll have to make the cost increase for the neighbours around the node as well - but only neighbours that are accessable by the node (can raycast between them without hitting any blocks)
Thanks Smiley




Offline pjt33
« Reply #7 - Posted 2014-06-24 14:45:36 »

I like Orangy Tang's idea a lot, but I'm going to throw a second idea into the ring, in case you're keen enough to try testing various ideas and see how effective they are. In short: meet in the middle.

This idea takes a parameter E (for excess) which indicates how much worse than optimal you're willing to accept. First find the optimal path length, L. Then, reusing the data structures you've already built up, extend into a breadth-first search of all nodes reachable from your start point in no more than EL/2 and with heuristic estimate no worse than EL/2. Now do a similar BFS from the end point. The intersection of the reachable points gives you paths of length no more than EL, and for each node in the intersection the path you get is the optimal path through that node.

The main downsides are that the two BFS will expand quite a lot more nodes than the original A*, and that you need to deduplicate. However, you'll probably need to do that with Orangy Tang's answer too unless you have a good heuristic for how much penalty to apply to each existing path, so without careful analysis or profiling it's hard to say which is faster.
Offline roland
« Reply #8 - Posted 2014-07-01 17:13:09 »

I took Orangy Tang's solution - I need to improve the heuristic a bit but it will work well. I will probably search for 4-5 paths and choose one at random, only 4-5x slower than always choosing the fastest path, which I can deal with.

Ingame Screenshot:  Smiley
Pages: [1]
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (29 views)
2014-12-15 09:26:44

Mr.CodeIt (20 views)
2014-12-14 19:50:38

BurntPizza (40 views)
2014-12-09 22:41:13

BurntPizza (75 views)
2014-12-08 04:46:31

JscottyBieshaar (37 views)
2014-12-05 12:39:02

SHC (50 views)
2014-12-03 16:27:13

CopyableCougar4 (47 views)
2014-11-29 21:32:03

toopeicgaming1999 (113 views)
2014-11-26 15:22:04

toopeicgaming1999 (100 views)
2014-11-26 15:20:36

toopeicgaming1999 (30 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29: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
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!