Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
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  
  [Help]Platformer Pathfinding  (Read 4371 times)
0 Members and 1 Guest are viewing this topic.
Offline Tom-Todd

Senior Newbie





« Posted 2012-05-06 17:48:34 »



I've been thinking about how to do path finding for my 2D platformer, I want the enemies to be able to find their way towards the player and jump on to higher platforms to reach them... I looked into the A* algorithm but it seems to be more suited to top down games and I was wondering if anyone had any good ideas regarding platformer pathfinding?
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #1 - Posted 2012-05-06 18:00:08 »

A* can be used on any graph to find a route from one node to another, not just top down maps. You just need to find a way of representing your platform level as a suitable graph that can be traversed.

Previously I've done that by generating waypoints at regular intervals along the surface of the platforms, then generating links between adjacent waypoints, like this:

Here, the greed diamonds are waypoints and the white lines the available routes between nearby waypoints. You'll need to generate links not just from waypoints on the same platform, but between waypoints on different platforms that you can jump between.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #2 - Posted 2012-05-06 18:23:09 »

I think, what Orangy Tang writes, is something really intresting, but I think you should go with a simplified AI, if that would fit your need:

Enemys just walk towards your player (in the direction to the player, which means either left or right), and if they have no ground below anymore, they just jump. Thats the simliest AI. It is used really often.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Tom-Todd

Senior Newbie





« Reply #3 - Posted 2012-05-06 18:28:42 »

Yeah, But that wouldn't really be what I was aiming to achieve, I know it's simplest, but it's not really what I'm looking for... I'll keep it in mind though thanks Smiley
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #4 - Posted 2012-05-06 18:29:35 »

Yeah, But that wouldn't really be what I was aiming to achieve, I know it's simplest, but it's not really what I'm looking for... I'll keep it in mind though thanks Smiley

In that case, I'd go with Orangy-Tang's Version Wink

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Tom-Todd

Senior Newbie





« Reply #5 - Posted 2012-05-07 00:14:39 »

A* can be used on any graph to find a route from one node to another, not just top down maps. You just need to find a way of representing your platform level as a suitable graph that can be traversed.

Previously I've done that by generating waypoints at regular intervals along the surface of the platforms, then generating links between adjacent waypoints, like this:

Here, the greed diamonds are waypoints and the white lines the available routes between nearby waypoints. You'll need to generate links not just from waypoints on the same platform, but between waypoints on different platforms that you can jump between.
How would I make this look natural, so the entity doesn't just fly there following straight lines, it jumps, and the jump curves like a normal jump...?
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #6 - Posted 2012-05-07 01:47:32 »

How would I make this look natural, so the entity doesn't just fly there following straight lines, it jumps, and the jump curves like a normal jump...?

The A* result will only describe the waypoints the enemy needs to take - how they actually navigate between the two waypoints is up to you. Ideally you want your waypoints to be dense enough that navigating from one to the next is trivial (eg. just move left or right, or jump in a direction).

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Damocles
« Reply #7 - Posted 2012-05-07 06:38:34 »

There are many ways to Rome.
What I did in Kobold Tournament 4k is to have the NPCs use the exact same physics as the player.
http://damocles11.byethost9.com/kobold.html

In order for them to reach the player or some position like the powerup, they try out (simulate) many combinations of movement-commands.

The combination resulting in the position closest to the target is chosen.
This is quite CPU intensive though.

But when combining this with an A* based search and a well defined navigation-mesh or waypoints, this approach looks very dynamic.

As your game will probably not have the enemies find you from like 100 tiles away, but follow you in close distance, an A* based actual
pathfinding might be overkill. In this case I would just give the AI some information about "jump-point" to reach a level above, and
else just walk into the direction closest to the player.

Offline Tom-Todd

Senior Newbie





« Reply #8 - Posted 2012-05-07 12:12:58 »

How would I go about simulating the movements?
It would mean anticipating collision, the NPCs knowing when/where to jump...
Also, in the future I want to have some team-mate NPCs who follow and fight with the player,
would a similar system work for this?
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #9 - Posted 2012-05-07 12:39:13 »

How would I go about simulating the movements?

The same way you simulate the movements for the player? We're rapidly getting into "write my game for me" territory I think. What have you tried? What didn't work?

For jumping, I originally had the enemy follow a bezier curve between the two waypoints. Later I changed it to just simulate a proper jump - finding the launch speed and angle is the only tricky bit, but that's just a bit of trig really.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Damocles
« Reply #10 - Posted 2012-05-07 12:40:51 »

What I did in the 4k game (since its 4 kilobytes, there was no way to insert a node-based pathfinding)
was to create an array of like 2 second movement-command sequences.
They where partly random, and partly based on some repeating patterns (like walking left for 1 secon, then jumping)

The commands included left,right,and jump, in like a 0.1sec resolution

In the n end, its basicaly just a sequence of how to move for the next 2 seconds.

I think I made like 100 sequences per AI to simulate.

Next, these sequences are taken and simulated (basically just moving the AI based on these commands, why applying the collisionphysics)
The endposition and possible HP reduction (lava) are evaluated.
The sequence wich brings the AI closest to the goal (other AI or pickup) is then favored as best movesequence.

Then the movesequence is executed for 2 seconds, until the next simulation is done.

The effect is that the AI can handle the environment very dynamic without knowing too much about it.
It will most of the time find a meaningful way, UNLESS the 2 seconds are not enough time (local maxima, the AI might walk to a trap-point)

It works well for the short-distance search.
But for long distance search you also would need to add some node-based pathfinding. The short distance AI can then be used to reach the waypoints calculated by the
long distance search.

Offline Tom-Todd

Senior Newbie





« Reply #11 - Posted 2012-05-07 12:46:42 »

Quote
The same way you simulate the movements for the player? We're rapidly getting into "write my game for me" territory I think. What have you tried? What didn't work?

For jumping, I originally had the enemy follow a bezier curve between the two waypoints. Later I changed it to just simulate a proper jump - finding the launch speed and angle is the only tricky bit, but that's just a bit of trig really.

What I meant was, I'm not simulating the movement for my player, I'm just moving them, by simulating I assume that means playing through possible movements without actually moving the NPC and seeing which one is best, I'm not asking anyone to write my game for me, as then I wouldn't learn anything and I couldn't feel pride in the final product, I'm sorry if it came across that way, but this is my first real game attempt and I'm new to this...
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.

Riven (13 views)
2014-07-29 18:09:19

Riven (10 views)
2014-07-29 18:08:52

Dwinin (10 views)
2014-07-29 10:59:34

E.R. Fleming (26 views)
2014-07-29 03:07:13

E.R. Fleming (10 views)
2014-07-29 03:06:25

pw (40 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (27 views)
2014-07-23 21:07:15

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!