On Tue, Dec 1, 2015 at 9:34 PM, <[email protected]> wrote:
> Okay I think I've got it?
>
...
>
> and then I understood what you meant, I could have just done:
> x = MoveTo(p,1)
> x += MoveTo(p2,1)
>
>
yes, that is.
> By the way,
> Regarding the A* algorithm itself, do you know of a more efficient of
> pathfinding?
> While the algorithm I'm using works very well, it's quite slow when trying
> to solve a maze for example, or go long distances, which halts the program
> for a few seconds until it's done computing. That makes the sprite jump a
> large distance at once..
> Also it hits a recursion limit when the distance is too high. so I have to
> raise it with:
> sys.setrecursionlimit(1500)
> Which is just a bummer.
>
> Maybe someone else did pathfinding more efficiently already?
>
>
>
With non-destructible walls, an approach based on the Floyd–Warshall
algorithm [0] is interesting
1. use Floyd–Warshall algorithm to calculate the matrix with the
minimum distances between ij vertices. Thats O(n**3), n the #vertices, but
being the walls inmutable it can be precalculated.
2. To move an actor in node i towards node j, you only need to examine
the neighbors of i : move to neighbor k if min_dist(i, j) == d(i, k) +
min_dist(k, j). Usually the #neighbors is low, so this is cheap to
calculate.
We used this in a pyweek game [1].
Whatever the basic pathfinding used, it can befurther accelerated by
combining with
Zoning / Level of Detail
---------------------------------
- Divide the map in zones, define a top level empty graph G
- add to G a vertex for each zone
- select a suitable vertex in each boundary between two zones, add the
vertex to G and also the edges between the boundary and both zones
Now navigation from i to j is a two level task
- if in the same zone, consider only the vertices in the zone
- if in different zones, first solve at the toplevel, G, so i would need
to go to boundary vertex q. ; solve i to q into the zone
- when actor arrives to q repeat the procedure for q,j
[0] https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
[1]
http://code.google.com/p/aiamsori/source/browse/trunk/gamelib/waypointing.py
--
You received this message because you are subscribed to the Google Groups
"cocos2d discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/cocos-discuss.
For more options, visit https://groups.google.com/d/optout.
