Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
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* plus gateways/teleporting equals death?  (Read 1731 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2011-12-26 22:30:00 »

Hello. I just got my A* pathfinding algorithm working well, and just as I was about to actually implement it into the game, I realized something. I want to be able to have portals, gateways and teleporting in my game, meaning that the fastest way to the target could be through a portal. At first, I figured that this would be as easy as adding an extra "neighbor" to the teleport nodes, but this would not work with A*, since the heuristic for each node is required to be less than or equal to the actual cost of the path from it to the goal. A portal may allow the unit to travel an extraordinary distance at a very low cost, which means that the heuristic would be inaccurate and worthless. Do I have to fall back to Dijkstra's, which is a lot less effective?

Myomyomyo.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2011-12-26 23:34:36 »

Do I have to fall back to Dijkstra's, which is a lot less effective?
Yes.


Or you could make your search algorithm more specialized, making the portals the destinations of your search(es) and in the next iteration, make them the source from where you (continue to) search the target. Once you found a couple of paths, join them together into a single path. It's not trivial to get this right, but it is probably much faster than 'bruteforce' Dijkstra.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #2 - Posted 2011-12-27 00:35:47 »

If its low numbers of portals you can do hacks like Riven said.

E.g. calculate shortest path via each possible portal and take smallest of the options (although if using several portals in an individual path, the combinations grow FAST).

You can hack this a little further by pre-computing the distance of each location to the nearest portal . The when computing a distance, you can calculate the shortest path, and then ignore portal usage if this distance is smaller than the nearest portal at either end of the path.

To really nail this problem, you pre-process, e.g. run something like Brandes inbetween centrality algorithm. But presumably you want to stick to whatever you have coded currently.


Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #3 - Posted 2011-12-27 16:11:25 »

The only code I have at the moment is a test program. I have yet to actually integrate it to the game I'm making.

I thought about keeping the portals in mind when calculating the heuristic value of each node. This would require me to do some pre-processing before each job, basically some pre-computed heuristics between portals based on the goal node. However, this is a similar problem to path-finding in itself, which means that I the pre-computing could get very very slow with many portals, possibly eliminating the gain from using the heuristics later completely (in an extreme case of course).

I have plans for some pretty advanced path-finding optimizations later, but for now, I'll just stick with Dijkstra's then. However the paths I get from Dijkstra's are pretty random and blocky, which might result in the path not being followed optimally by units since they aren't limited to 4 or 8 directions like the path-finding is. I think I need some kind of tie-breaker, but how is this implemented? I want a more straight line between corners. Currently (assuming 8 neighbors per node) it first only walks diagonally until it gets to the same X or Y as the target and then walks axis-aligned to the target, like this:

The light blue/teal node is the goal.

I obviously want it to move in a line towards when moving across larger spaces. How would I accomplish this? Obviously, such a path would have the exact same cost, but simply not be selected because the path above is the path it would find first.

Myomyomyo.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #4 - Posted 2011-12-27 20:12:54 »

How static/dynamic are the portals? It sounds like hierarchical A* would be a good fit: http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline theagentd
« Reply #5 - Posted 2011-12-27 20:43:07 »

How static/dynamic are the portals? It sounds like hierarchical A* would be a good fit: http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf
Well, great. Thanks. I thought *I* came up with the idea of hierarchical A*. I'll just add it to my "Already invented algorithms I've come up with"-list, right under ray-marched volumetric lighting and depth peeling. Cry Cry Cry


...

Everything is dynamic (but not changing too often), including walls and terrain cost, so hierarchical A* would work fine as we don't have to reprocess the whole map on each change.

Myomyomyo.
Offline ReBirth
« Reply #6 - Posted 2011-12-28 13:08:50 »

How static/dynamic are the portals? It sounds like hierarchical A* would be a good fit: http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf
that pdf is a good read.

oot, where do you guys got above pic? it's funny.

Offline theagentd
« Reply #7 - Posted 2011-12-28 16:11:34 »

oot, where do you guys got above pic? it's funny.
xkcd.com

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

Dwinin (19 views)
2014-09-12 09:08:26

Norakomi (54 views)
2014-09-10 13:57:51

TehJavaDev (63 views)
2014-09-10 06:39:09

Tekkerue (31 views)
2014-09-09 02:24:56

mitcheeb (53 views)
2014-09-08 06:06:29

BurntPizza (37 views)
2014-09-07 01:13:42

Longarmx (23 views)
2014-09-07 01:12:14

Longarmx (27 views)
2014-09-07 01:11:22

Longarmx (26 views)
2014-09-07 01:10:19

mitcheeb (34 views)
2014-09-04 23:08:59
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!