Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (480)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (547)
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  
  Moving target path finding  (Read 1004 times)
0 Members and 1 Guest are viewing this topic.
Offline Z-Man
« Posted 2013-05-11 04:28:19 »

In working on implementing better pathfinding than "which way is it? ok go that way." I decided to start with A* as I've heard it mentioned before. A* might be a bit overkill for a grid-based game where you can only move in four directions, but oh well. Unfortunately after getting it working I discovered that a basic A* implementation doesn't work very efficiently when the target is moving around. So, I'm trying to figure out a better way to get my enemies to find their way to the player with out getting stuck. If anyone has suggestions, or experience with doing something like this I'd love to read it Grin
Offline HeroesGraveDev

JGO Kernel


Medals: 244
Projects: 11
Exp: 2 years


┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻


« Reply #1 - Posted 2013-05-11 04:33:37 »

What I did for Guardian II is this:

1. Check if target is alive. If not, cancel.
2. If target is targetable with simple AI, switch to simple AI. Otherwise, continue:
3. Check if path to target has been found. If not, find a path.
4. Check if you are on the path. If not, try to get on path. If still not, find new path.
5. Check if target is within a certain distance of the path's end point. If not, find a new path.
6. If at end point and target not targetable with simple AI, find new path to target.

By 'simple AI' I mean, if target is left, go left. If target is right, go right etc.

Offline ReBirth
« Reply #2 - Posted 2013-05-11 10:52:44 »

Little tips, you should separate entities into separate lists based on its type (alive, movable, etc) so it can reduce the looping time, since you need to perform this a lot.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline jam

Senior Newbie





« Reply #3 - Posted 2013-05-11 16:42:44 »

Are you setting the actual "moving target" as target or some sort of simple prediction? (Like p.e. x tiles into the direction the target is walking, where x is the distance between the chasing entity and the target now)

Depending on how much cpu you can afford to waste and how you want your entities to "react", you can get some neat looking "behaviour" by just messing around a little with the way the fake/prediction-target gets chosen or even comparing multiple fake targets (doing pathfinding from target to its potential goals first + choosing something on that path as target instead of the actual target itself can have neat results too).

If something like that makes sense can depend a lot on exactly how your game / levels look though, so maybe you should post a screen-shot or something in the hope that someone who's more experienced that me can give you more specific advice. Wink
Offline Z-Man
« Reply #4 - Posted 2013-05-11 17:35:28 »

Little tips, you should separate entities into separate lists based on its type (alive, movable, etc) so it can reduce the looping time, since you need to perform this a lot.
Thanks for the tip. I've already done this in the way that path finding for each entity is done.

Are you setting the actual "moving target" as target or some sort of simple prediction? (Like p.e. x tiles into the direction the target is walking, where x is the distance between the chasing entity and the target now)

Depending on how much cpu you can afford to waste and how you want your entities to "react", you can get some neat looking "behaviour" by just messing around a little with the way the fake/prediction-target gets chosen or even comparing multiple fake targets (doing pathfinding from target to its potential goals first + choosing something on that path as target instead of the actual target itself can have neat results too).

If something like that makes sense can depend a lot on exactly how your game / levels look though, so maybe you should post a screen-shot or something in the hope that someone who's more experienced that me can give you more specific advice. Wink
Currently I'm just setting the "moving target" to the target's actual location. I'll play around with estimating where the target would be after x number of moves though, thanks for the suggestion Smiley I'm not sure how helpful a screenshot would be, as I don't have any of the final level designs done. I'm currently in the process of implementing features.

What I did for Guardian II is this:

1. Check if target is alive. If not, cancel.
2. If target is targetable with simple AI, switch to simple AI. Otherwise, continue:
3. Check if path to target has been found. If not, find a path.
4. Check if you are on the path. If not, try to get on path. If still not, find new path.
5. Check if target is within a certain distance of the path's end point. If not, find a new path.
6. If at end point and target not targetable with simple AI, find new path to target.

By 'simple AI' I mean, if target is left, go left. If target is right, go right etc.
I hadn't thought about separating it out into a simpler AI and a more complex one. However, I'm worried that determining if simple AI will work and then having to resort to complex AI would just worsen the performance problems. Perhaps I'm misunderstanding your explanation though.
Offline HeroesGraveDev

JGO Kernel


Medals: 244
Projects: 11
Exp: 2 years


┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻


« Reply #5 - Posted 2013-05-11 19:17:07 »

With ~200 goblins and ~19 heroes running around using the AI it seems to work fine. Smiley
Not to mention the heroes are switching targets between enemies and following the player every few seconds.

I'll give you a snippet of the code in an hour or so.

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.

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

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

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

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

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

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

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

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

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
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!