Hi !
Featured games (84)
games approved by the League of Dukes
Games in Showcase (603)
Games in Android Showcase (171)
games submitted by our members
Games in WIP (652)
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  
  PathFinding with gravity  (Read 1740 times)
0 Members and 1 Guest are viewing this topic.
Offline Beppe

Junior Devvie

« Posted 2013-09-12 16:50:57 »

Hi ,
it's the first time that I must handle this argument ... so I have seen some tutorial about pathfinding , but nothing with gravity ... Some links??
Offline UprightPath
« Reply #1 - Posted 2013-09-12 18:13:34 »

I'm not sure that there's a specific link to doing path finding with gravity (I know people have spoken about it here before, but it's been some time). However, it's possible to do so.

Just like in regular path finding the most important part is defining the map. In this case, instead of defining the map as a set of connected tiles you define it as a set of arcs along which an entity can move. Most of these arcs will be flat likes which describe the 'walkable' ground while others would be the arcs of jumps that take the entity from one surface to another. The major issue is figuring out where the end points of these arcs are. The visualization of the map would look something like this:

When someone gets knocked off a surface or they jump before an edge, you check for the next closest surface beneath them and that'll be the arc that they're on for the path finder.

Offline Several Kilo-Bytes

Senior Devvie

Medals: 11

« Reply #2 - Posted 2013-09-12 23:50:42 »

What kind of path finding? Optimal or non-optimal? Do you need true path finding or just hazard avoidance?

Path finding with forces is hard because you have to account for velocity, increasing two or three dimension spaces to four or six. If you have a platformer where you can jump with no mid air control, then you can still use A* by treating jumps as graph edges and starting/landing places as nodes. Grid based solutions don't work because there is more than one way to get to a physical location and thus different places you could land by passing through a space at different speeds. This is why the search space has a higher dimension and the extra dimensional search space is what makes it more complex.

Rapidly exploring random trees can be used for path finding in higher dimensions. There is a good example on the web page documenting them. They give non-optimal and are non-deterministic, but are simple.

There is also the Mario AI contest. Some of the algorithms are based on A*. Much of the code is in Java as well as the "Infinite Mario" game it works with. There is a "famous" website and YouTube videos for one competitor in a previous year that illustrates how it works. I don't have the link but it is searchable.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Beppe

Junior Devvie

« Reply #3 - Posted 2013-09-16 14:17:00 »

Not so difficult, guy Cheesy.... I have a simple tile based game , and there is no jump the only thing to consider is the gravity , so  enemy mustn't fly and for increase his y cordinate he must climb a stair...
So I've look to a tutorial about Breath First ... but it is for a tile based game without gravity and is very expensive calculate a path every gameloop's cycle...
Offline UprightPath
« Reply #4 - Posted 2013-09-16 14:41:58 »

How does gravity come into the equation then? Falling off of edges?

Basically, you have to define your graph. This is different (Not always, but often is) from your tile map. The graph indicates where there are transitions between states (A state, in this case, being a position on the tile map). After you have defined your graph you can then apply any number of search algorithms (Also known as path finding algorithms) to this graph.

If you're worried about efficiency then you'll have to look into the various 'fast' path finding methods such as Best First, A*, etc.. These will cut down on the number of nodes expanded (Makes it faster) but you might be better off with other AI methods if you're worried about Frame-by-Frame path finding (This will always be very expensive and often very wasteful.)

Offline Beppe

Junior Devvie

« Reply #5 - Posted 2013-09-16 15:13:51 »

yes .... it control when move the sprite right or left if it is out of edge... every Tile have some states for example walkable (true or false) ladder (true or false) ecc ecc ..
Offline Several Kilo-Bytes

Senior Devvie

Medals: 11

« Reply #6 - Posted 2013-09-16 23:07:43 »

If you ignored the other web pages because they didn't mention your specific case, then go back and learn them. Learn what the breadth first search is then learn what makes A* faster while still preserving optimality. Also learn what optimal path means.

The generic grid method still works if you are sufficiently constrained. (To discrete grid location, with no jumping, and with constant speed when not stationary.) If take away constraints then you increase the search space. That basically just means your search nodes contain an extra variable, but it could multiply the size of your search space by the number of values your third variable could take - in the worst case scenario. If the character is free moving, then it gets much harder.

A* is fast enough to do once per update cycle if your search space is small. Complexity grows faster then search space, so don't use tiles that are only one pixel. Tiles are typically big, so there are only so many that can fit on the screen that are also reachable. There is no practical reason to recompute paths every frame anyway. It's not as if it will change each moment.
Offline Beppe

Junior Devvie

« Reply #7 - Posted 2013-09-19 15:06:05 »

So breadth first work and the path is correct but i've problem to move enemy following path ....
I follow this tutorial :
But it don't convince me ... because if moveChar is called every Frame , and we assume that path have 6 tile and every tile is 20 pixel and my enemy's speed is 2pixel  after 6 frame path array is empty but the enemy is moved only for 12pixel , not only if in the third tile for example enemy must climb up on a stairs , he is moved for only 6 pixel and so he cannot be in the right tile(the stairs tile)....
Offline UprightPath
« Reply #8 - Posted 2013-09-19 16:44:21 »

But it don't convince me ... because if moveChar is called every Frame , and we assume that path have 6 tile and every tile is 20 pixel and my enemy's speed is 2pixel  after 6 frame path array is empty but the enemy is moved only for 12pixel , not only if in the third tile for example enemy must climb up on a stairs , he is moved for only 6 pixel and so he cannot be in the right tile(the stairs tile)....

For this you'd use something of a 'way point' system. Basically, treat your path as a set of goals for the character/enemy to move to. When it gets to a goal tile, you remove it from the list and it tries to get to the next one. You'd only need to find a new path when the goal is no longer in the same place (Think if you're trying to get to the player and they just stand still, should have o get a new path each time?)

Offline Beppe

Junior Devvie

« Reply #9 - Posted 2013-09-19 19:46:56 »

I have understand the general sense but pop of the queue is done every time move is called , so if  my enemy speed is 1 and a tile is longer when i call moveChar the second time the target is the third tile but enemy is still in the first...
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

SHC (17 views)
2015-08-01 03:58:20

Jesse (17 views)
2015-07-29 04:35:27

Riven (38 views)
2015-07-27 16:38:00

Riven (20 views)
2015-07-27 15:35:20

Riven (22 views)
2015-07-27 12:26:13

Riven (13 views)
2015-07-27 12:23:39

BurntPizza (32 views)
2015-07-25 00:14:37

BurntPizza (44 views)
2015-07-24 22:06:39

BurntPizza (25 views)
2015-07-24 06:06:53

NoxInc (33 views)
2015-07-22 22:16:53
List of Learning Resources
by gouessej
2015-07-09 11:29:36

How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30

Intersection Methods
by Roquen
2015-05-29 08:19:33

List of Learning Resources
by SilverTiger
2015-05-05 10:20:32

How to: JGO Wiki
by Mac70
2015-02-17 20:56:16

2D Dynamic Lighting
by ThePixelPony
2015-01-01 20:25:42

How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21 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‑
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!