Skip to main content ↑ ↓
Topic: Pathfinding (Read 129808 times) previous topic - next topic
0 Members and 3 Guests are viewing this topic.

Pathfinding

Post some useful links regarding pathfinding algorithms and such here! Also repost your stuff that got lost in the crash either on the wiki or as a GitHub Gist and link/embed it here :)

An open-source A-star implementation in JavaScript by Brian Grinstead with an excellent demo - http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript-updated (its GitHub repo)

Basically, his pseudocode went from...

Code: [Select]

  push startNode onto openList
  while(openList is not empty) {
     currentNode = find lowest f in openList
     if currentNode is final, return the successful path
     push currentNode onto closedList and remove from openList
     foreach neighbor of currentNode {
         if neighbor is not in openList {
                save g, h, and f then save the current parent
                add neighbor to openList
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
         }
     }


to... (* denotes changed lines)

Code: [Select]

  * push startNode onto openHeap
  while(openList is not empty) {
     * currentNode = pop from openHeap
     if currentNode is final, return the successful path
     * set currentNode as closed
     foreach neighbor of currentNode {
         * if neighbor is not set visited {
                * save g, h, and f then save the current parent and set visited
                * add neighbor to openHeap
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
                 * reset position in openHeap (since f changed) 
         }
     }


...and it's now leaps and bounds faster. I don't know off the top of my head how fast Beaker's most recent JS pathfinding was or Radnen's last released version, but this guy's seems pretty fast. The GitHub repo (and a later blog post) also has discussions on adding weight to nodes for stuff like simulating terrain penalties (eg, takes 2 steps to go through a desert tile instead of 1 step to go through a plains tile). This fork by GitHub user Hankus (which I believe was later merged) demonstrates adding weight and allowing diagonal movement.

Brian's Gist for the updated version with node weights (0 = closed, >0 = weight/movement cost):

[gist]581352[/gist]

Re: Pathfinding

Reply #1 –
Mines really fast since it uses a binary tree and efficient table lookups. Mine should be no faster than his, algorithmically.

[gist]5406961[/gist]

It's also has the ability to set the comparer to something else, so that you can add weights to it. :)
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Pathfinding

Reply #2 –
@Radnen re gist/pathfinder.js - even though your game function is a simple example, I'd still recommend taking a call like GetSystemUpArrow out of the loop.

Re: Pathfinding

Reply #3 –
Quote from: N E O – on

@Radnen re gist/pathfinder.js - even though your game function is a simple example, I'd still recommend taking a call like GetSystemUpArrow out of the loop.


Why? What problem does it solve by taking that out of the loop? We've already discussed that the GetSystem*() functions do not send out a copy each time. There's really no fear of a memory leak or anything.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Pathfinding

Reply #4 –
Wasn't Jester intending on changing it so that GetSystem* made new copies in case on-the-fly edits were made to pixels or something?

Re: Pathfinding

Reply #5 –
I double checked yesterday the behavior of GetSystemFont() in sphere1.6 and it produces copies on each call. I checked by setting the color of the font.

Re: Pathfinding

Reply #6 –
Alright, I changed it. I guess the behavior of those calls have changed.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Pathfinding

Reply #7 –
I have a slow (uses a simple array, I'm updating it to a binary heap) and likely slightly buggy A* pathfinder. The only notable part is that it can automatically create a tile obstruction grid of the map, when using the default map engine. This is slightly ugly, and is only over tiles, not pixels (I was getting out of memory errors with a per-pixel grid), but works pretty well.

I'm going to update the algorithm to JPS, which will easily blow any A* pathfinder out of the water performance wise. JPS is possibly fast enough to do pathfinding in pixel space, so I'm trying to develop an approach to avoid running out of memory for large grids, by storing information directly in 32 or 64-bit (actually a pair of 32-bit) integers.

Re: Pathfinding

Reply #8 –
Quote from: alpha123 – on

I have a slow (uses a simple array, I'm updating it to a binary heap) and likely slightly buggy A* pathfinder. The only notable part is that it can automatically create a tile obstruction grid of the map, when using the default map engine. This is slightly ugly, and is only over tiles, not pixels (I was getting out of memory errors with a per-pixel grid), but works pretty well.


Why create an obstruction map beforehand? My pathfinder doesn't do this, but it could check while processing, like Beakers. When it visits a node at, say tile (5, 4), then only at that point checks 'IsObstructedAt(name, 5*16, 4*16)' this will take a bit more processing, but less memory lying around. If you move to JPS this would be ideal.

Quote from: alpha123 – on

I'm going to update the algorithm to JPS, which will easily blow any A* pathfinder out of the water performance wise. JPS is possibly fast enough to do pathfinding in pixel space, so I'm trying to develop an approach to avoid running out of memory for large grids, by storing information directly in 32 or 64-bit (actually a pair of 32-bit) integers.


And holy cow, JPS looks awesome. I would love to see this implemented in Sphere. It hasn't yet been done so I'd say try it out. A Per-pixel quadtree version had been made by Kamatsu, but he said it was too slow, even though it should have technically been more than fast enough in any other programming environment (check out his tech demo 'digger'?) I might upload it to the repo if I still have it.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: Pathfinding

Reply #9 –
Quote from: Radnen – on

Why create an obstruction map beforehand? My pathfinder doesn't do this, but it could check while processing, like Beakers. When it visits a node at, say tile (5, 4), then only at that point checks 'IsObstructedAt(name, 5*16, 4*16)' this will take a bit more processing, but less memory lying around. If you move to JPS this would be ideal.

Ha, I never really thought of that... that would indeed solve all my problems! One of the benefits it currently has is that the grid can come from anywhere, not just the map, but I'm sure it would be fairly easy to generalize it a bit (make IsObstructedAt a parameter or something).
Won't the closed list eventually get big enough that it would still run out of memory though? I think I'll still do the integer packing, even if I compute the obstruction grid on demand, just to be extra memory efficient. Memory is definitely the bottleneck here, not processing speed (especially with JPS in tile space).

The way it currently makes an obstruction map is zoom an invisible person around every tile and check if it's obstructed. I'm not really sure if that would work with on-demand processing. It really seems like there's a better way to do this. Any suggestions?

Quote

And holy cow, JPS looks awesome. I would love to see this implemented in Sphere. It hasn't yet been done so I'd say try it out. A Per-pixel quadtree version had been made by Kamatsu, but he said it was too slow, even though it should have technically been more than fast enough in any other programming environment (check out his tech demo 'digger'?) I might upload it to the repo if I still have it.

Kamatsu's basically the Chuck Norris of algorithms. :P I saw the Digger demo; it was amazing (like pretty much everything else he touched...).
Huh, I never knew a quadtree could be used for pathfinding. I'll have to check that out. So basically it just does A* using a quadtree for the open and closed lists? (Does that even make sense?) Or is it instead of a grid? I'm definitely going to look this up. Heck, I don't even know what a quadtree is (well, I've heard of it, but that's about the extent of my knowledge).
Gee, I really need to be less weak with algorithms. :(

EDIT: Okay, I looked up quadtrees and how they relate to pathfinding. It's a really cool approach. I'm wondering if I could get it to work somehow with JPS (theoretically it shouldn't work any differently, though I'm still not sure I understand the whole thing).
 

Re: Pathfinding

Reply #10 –
Quote from: N E O – on

Wasn't Jester intending on changing it so that GetSystem* made new copies in case on-the-fly edits were made to pixels or something?


Yes, but not only because of that. Since not only the in-script copy itself, but the file or even the configuration of which file is the specified system resource (although this is only checked at startup in TurboSphere) is allowed to change at any time, it's safer to make no assumptions.