Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (727)
Games in Android Showcase (217)
games submitted by our members
Games in WIP (796)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Precomputed tile paths for pathfinding?  (Read 11900 times)
0 Members and 1 Guest are viewing this topic.
Offline pixelprime

Junior Devvie

Medals: 3

« Reply #30 - Posted 2012-03-07 00:14:57 »

You mentioned, earlier, that you were thinking about how it'd work if it were ported over to a mobile device. To me, that means touch screen controls for the most part.

Correct, that was my intial reason for adding mouse support to the game. Mouse clicks on tiles can be replaced by W,S,A,D movement on PCs, and mouse clicks on enemies to attack, pick up items or such can also be replaced by key presses (or the mouse!). Thus, touch screen capability is retained.

With regard to the static map; I refer to my earlier post regarding the possibility for only slight differences in the walkability of any particular calculated path. Would it be fair to assume that if the path is being traversed one node at a time (after the correct route has been calculated) that it would be fairly trivial to do a quick per-node check to see if the approaching tile is still walkable?

This goes back to my A- > B -> C example, but I think it's still relevant in this instance.

I'm not necessarily backtracking on my decision to go A* on this project; but I think it's worth considering all options in the event that I want to take a little from column A, and a little from column B.
Offline UprightPath
« Reply #31 - Posted 2012-03-07 00:24:04 »

It's probably rather trivial to do a check on the path to see if it's still open (Visibly open would be better). However, it depends on how long you're planning your paths in front of you. If you're going partial pathing. Like, in the RIH thing, only finding the real path across a room when you're in it, then it's probably not too bad to see if your current path is open. If you're getting the full path and checking it each time, then there's a good chance you're going to be path thrashing. Especially of enemies respawn.

What I mean there is, say, you get the whole path from where you are to another room. And let's say you pass through at least one other room to get there. If there's an enemy in that room, moving around. Each iteration you:
1) Check if the path is blocked.
2) If blocked, find another path.

If an enemy keeps walking over your path and you path find every tick.. You get the idea.

Offline Nyhm

Senior Devvie

Medals: 3
Projects: 1

Island Forge

« Reply #32 - Posted 2012-03-07 01:02:00 »

718 paths tested?!?

That's probably 'Nodes visited'. A* provides the best efficiency under optimal conditions. If it's not an optimal condition (There is no straight line to the goal), then it'll still be moreefficient than other options.

Because of the backtracking/straight line deviation that you created, it'll exercise a lot more nodes at the start. If you were to have a more direct path, it'd find it much more efficiently.

I'm sure I can improve my implementation, but UprightPath is correct: "Nodes visited" would be more clear. My implementation calls each potential end-point a path, so I'm checking each path to see if it ends at the goal. Sometimes you can see the algorithm appear to wiggle away from the destination, because the shortest path might still be in the opposite direction from the goal (as the crow flies). Ultimately, it will find the most efficient path (and at least as efficiently as other algorithms). I proved that in school once, but I'm just going to take everyone else's word for it at this point.

This implementation is a simple, 8-directional, non-weighted A*. In my game, it does a good job even when navigating through lots of obstacles (like over a river and through the woods). However, I put a wall-clock timeout on the processing. If it can't find a path in that time, I cancel the pathing, and the player has to walk a bit further "manually." This is justifiable because the pathfinder shouldn't be doing all the exploration (ok, that's really just an excuse).

Next time I have a cup of coffee, I'm going to pour through this discussion for all the keen pathing lore.

Island Forge: Create Islands with Stories for Others to Explore!
Free-to-Play with Membership and Upgrade options!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Nyhm

Senior Devvie

Medals: 3
Projects: 1

Island Forge

« Reply #33 - Posted 2012-03-07 01:15:50 »

Pathing an avatar toward a potentially far-away moving target (creature): The brute-force (and most precise) method is to re-path every step. Then you know you're always on the optimal path to the target's current position. This can be very CPU intensive (depending on the map).

Instead of repathing, I compute the path once, then walk along the path until you encounter (maybe with some radius of contact) the target. In the vast majority of cases (in my game), the enemy is charging at you, and the path is cut short. In cases where the enemy has moved away to another position (maybe it's chasing someone else), the character ends up at the enemy's initial position. At this point, I re-path to the new position, which is not usually very far away.

To improve this, a heuristic could be included: When the enemy's current position is some distance from the current path's endpoint (and not on the current path), cancel and repath. I haven't actually implemented that step yet (because it's a rare occurrence), but it sounds like a slight improvement.

Island Forge: Create Islands with Stories for Others to Explore!
Free-to-Play with Membership and Upgrade options!
Offline UprightPath
« Reply #34 - Posted 2012-03-07 01:23:12 »

Well, I was more talking about an interrupted path to a tile, not to a target.

Especially since he described enemies as oscillating instead of moving with a purpose. So, if you're pathing across a large map, and computing the whole path and checking it for interruptions the whole way, an oscillating enemy will cross/interrupt the path multiple times. And there's a high likely hood that the new path produced will shortly be moved in.

For moving towards a target, I'd run a check through the path to see if it's within some percent of the current distance left... So, say..

You plot the path to an enemy. At each logic check, you compute the heuristic distance (Should cost O(1)) from each point in your path to the enemy. If the lowest distance is less than say half the distance left in your path, you don't repath. If it's more, you repath to the target.

This means that you'll tend to repath only when you get closer to the target, and when you start having to repath, it'll be a shorter path each time.

Of course, you could only start checking when the heuristic distance between yourself and the target is less than some threshold.

Offline Nyhm

Senior Devvie

Medals: 3
Projects: 1

Island Forge

« Reply #35 - Posted 2012-03-07 01:41:52 »

I agree, that's a great way to go about it. I wasn't offering a contradiction/alternate to your above concepts - I was just bringing up a different scenario, which is how things play out in my game. Lot's of really interesting material here.

Island Forge: Create Islands with Stories for Others to Explore!
Free-to-Play with Membership and Upgrade options!
Offline pixelprime

Junior Devvie

Medals: 3

« Reply #36 - Posted 2012-03-07 10:58:32 »

I think there's a degree of complexity on assumption here that isn't necessary for the project I'm working on.

I agree that the inherant problems with pathfinding in a node system where blockages and interruptions are present can be cumbersome and difficult to overcome, but I'm taking an approach that removes most of these problems completely. How?

By stopping the player.

Let's say you want to go from point A to point G, and an appropriate path is calculated. Along the route, say, at tile D, you come across an enemy. In the above examples, people are generally suggesting methods of recaculating the path based on this (possibly new) obstruction and thereby increasing the load on the pathfinder.

However, my aim here is to simply halt the player and cancel out any further movement along that path. It's then up to the player to either deal with the obstacle (fight it) or go somewhere else.

I appreciate this might seem like a dumbed down idea, and certainly one ignominious to the normal practices of pathfinding, but in reality - I'm not looking for a graceful solution where the player's path can anticipate, overcome or circumvent dynamic obstacles. Simply bumping up against the obstacle en-route and stopping is more than sufficient for my needs.

In many ways, there are some benefits there. Clicking inside a room, only to have your player stroll over and bump up (and stop) against the door leading to that room, only serves to reinforce the fact that the player cannot simply 'stroll where they want' using this method. And, in fact, I would also say that as a player I would expect a pathfinding algorithm to at least attempt to take me as far as it possibly can (i.e. the door), leaving me to realise what I need to do to proceed to that area.

Too many times in C&C games I've ordered my units to a position on the map, and they've instead wandered off and wedged themselves next to a cliff - leaving me to wonder if that's actually intentional, and whether there's a blockade I need to deal with to proceed.

In my example above, the pathfinder assumes the player has a clear route to the room, but when the door is encountered, they are stopped. If the door is the only route in, then the pathfinder is actually technically finding the best route to the door, since that's where they'll be stopped, which is actually a desired artefact of this kind of dynamic perception of the local surroundings.

Hmm, that was perhaps a little more verbose than I'd intended. But in summary:

- The player does not need to circumvent dynamic obstacles (e.g. moving enemies), only be stopped by them
- The player will analyse surrounding obstacles during their path traversal
- It is not essential that the player (or in fact any moving enemy) is omniscient enough to predict obstacles before they become so, only that they are seen just before the moment of impact.

I should imagine this simplifies the solution somewhat, as the pathfinding will always take place on the entire walkable surface of the map, and the (carefully selected) obstructions will be dealt with in real-time during the course of the path movement.
Offline Damocles
« Reply #37 - Posted 2012-03-07 11:31:09 »


For an RTS I usually use a floodfill pathfinding. (given that The grid is not too big, like 100x100 the performance is ok)

There are 2 advantages:

#1 An unlimited number of units can use this single path-map at the same time - given they want to reach the same destinationpoint.
 (Moving a group, with members spread at random locations)

#2 The units can avoid dynamic obstacles without the need to recalculate the path

How its done:

You basically fill the map from the destinationpoint with "height" values. Just like filling an image with a color in a paintprogram.
This creates a topography.
The algorythm continues until no "untouched" passable field ist found.

Every new filled tile gets increased in "height" by one given the closes filled neighbors height +1.

Now when the unit walks to the destination (wich is at the bottom of the "hill") It just needs to move to the neighboring field wich
has the lowest hightvalue.

The good thing: it does not matter where the units start from. There will always be a lower field to go to from anywhere on the map.

When this field is blocked by a dynamic object, it just chooses another field.
In case there are bigger obstacles it could increase the height of the field its standing on by 1, thus filling possible dynamic traps.
(altering the topography)

You could even make the unit avoid dangerous regions, like an enemy base by increasing the fields-height there.
This makes these area last to be chosen if no other path is free.

(I have an implementation somehwere here in the sourcecode for CraftCraft 4k.)

Its slower than A* for a single path, but as stated it more efficient when dealing with many units, and dynamic obstacles.

The algorythm is also quite simple to code.

You could even increase the performance by precalculating a list of "standard" destination points , choose the one closes to the actual destnation and let A* take over on the
short distance.
This way you can have hundrets of units walk on a map with almost not CPU power needed.
(trading Memory for Performance )

Pages: 1 [2]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Archive (298 views)
2017-04-27 17:45:51

buddyBro (486 views)
2017-04-05 03:38:00

CopyableCougar4 (931 views)
2017-03-24 15:39:42

theagentd (945 views)
2017-03-24 15:32:08

Rule (955 views)
2017-03-19 12:43:22

Rule (924 views)
2017-03-19 12:42:17

Rule (925 views)
2017-03-19 12:36:21

theagentd (988 views)
2017-03-16 05:07:07

theagentd (899 views)
2017-03-15 22:37:06

theagentd (695 views)
2017-03-15 22:32:18
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51 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!