Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (552)
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* path finding being slow  (Read 696 times)
0 Members and 1 Guest are viewing this topic.
Offline Quadro

Senior Newbie





« Posted 2013-01-19 14:58:40 »

This isn't a question about making an A* path finder, I already have one I made for my game, the only problem is it takes a bit of time to process paths around hook shaped objects, all I'm doing is looping through the last tiles I added and then branching out like explained on Wikipedia, is this a common thing for A* or should I optimize it

I don't know if this will look right but here is the shape I'm talking about, P is player X is the clicked spot
1  
2  
3  
4  
5  
......................................................
......................######.........................
..................###.................................
...P.........##....................X................
..........##........................................
Offline actual

JGO Coder


Medals: 23



« Reply #1 - Posted 2013-01-19 15:11:07 »

If that hook is a static part of the terrain you can do what some people refer to as waypoint or point of view pathfinding. That is you place a "waypoint" or marker at the top of the hook, or at some gap. If you want to go "through" the hook, you then first A* to the way point (which should be pretty quick) and then once you are at the way point you A* to your target on the other side.

Google "waypoint pathfinding" or "point of view pathfinding" for more information. I haven't done much with pathfinding only read about it.
Offline Quadro

Senior Newbie





« Reply #2 - Posted 2013-01-19 16:23:21 »

If that hook is a static part of the terrain you can do what some people refer to as waypoint or point of view pathfinding. That is you place a "waypoint" or marker at the top of the hook, or at some gap. If you want to go "through" the hook, you then first A* to the way point (which should be pretty quick) and then once you are at the way point you A* to your target on the other side.

Google "waypoint pathfinding" or "point of view pathfinding" for more information. I haven't done much with pathfinding only read about it.


Thanks, I'll try that                                                 
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Best Username Ever

Junior Member





« Reply #3 - Posted 2013-01-19 17:00:12 »

If done correctly, your A* algorithm should expand the following nodes. 'e' marks nodes that were explored. 'v' marks nodes that were visited. You can further improve efficiency on static square grid spaces, but those obstacles aren't that bad for the vanilla algorithm to work with every once in a while millisecond (or less).

1  
2  
3  
4  
5  
......................................................
............eeee......######..........................
...eeeeeeeeevvvvee###eeeeeeeeeeeeee...................
..ePvvvvvvvvv##vvvvvvvvvvvvvvvvvvvvX..................
...eeeeeee##vvvveeeeeeeeeeeeeeeeeee...................

Offline Quadro

Senior Newbie





« Reply #4 - Posted 2013-01-19 18:57:39 »

Thanks guys, I realized that I had a for loop checking every single tile thousands of times if My A* path finder had logged that coordinate already, I ended up adding some debugging stuff to highlight tiles visited and I realized what was happening, now it works flawless with no wait
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.

CopyableCougar4 (23 views)
2014-08-22 19:31:30

atombrot (34 views)
2014-08-19 09:29:53

Tekkerue (30 views)
2014-08-16 06:45:27

Tekkerue (28 views)
2014-08-16 06:22:17

Tekkerue (18 views)
2014-08-16 06:20:21

Tekkerue (27 views)
2014-08-16 06:12:11

Rayexar (65 views)
2014-08-11 02:49:23

BurntPizza (41 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (41 views)
2014-08-06 19:49:38
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!