Created
June 15, 2019 22:02
-
-
Save greysondn/cad4fc90c80613752985a3826e83b21f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Tile | |
| { | |
| // things go here | |
| } | |
| class PathNode | |
| { | |
| public var tile:Tile = null; | |
| public var previous:PathNode = null; | |
| public var distance:Int = null; | |
| public function new(til:Tile, prev:PathNode, dist:Int) | |
| { | |
| this.tile = til; | |
| this.previous = prev; | |
| this.distance = dist; | |
| } | |
| } | |
| // somewhere | |
| public function findPath(first:Tile, last:Tile) | |
| { | |
| // create a node for the starting point | |
| var start:PathNode = PathNode(first, null, 0); | |
| // to go nodes | |
| var remaining:Queue<PathNode> = new Queue<PathNode>(); | |
| // you need a structure for the remaining ones in many languages because | |
| // the references aren't enough to prevent garbage collection. YMMV. | |
| // queue is already imported - why not? (Actually check if you shouldn't) | |
| var checked:Queue<PathNode> = new Queue<PathNode> | |
| // now it gets fun | |
| var notFound:Bool = true; | |
| var finish:PathNode = null; | |
| // put start at back of queue | |
| remaining.push(start); | |
| // actual meat of search process | |
| while (notFound && !remaining.empty()) | |
| { | |
| // pull node off front of queue | |
| var current:PathNode = remaining.pop(); | |
| // check to see if we've found the end | |
| if (current.tile = last) | |
| { | |
| // stop searching! | |
| notFound = false; | |
| finish = current; | |
| } | |
| else | |
| { | |
| // prepare for next step of search | |
| if (current.tile.north != null) | |
| { | |
| remaining.push(new PathNode(current.tile.north, current, current.distance + 1)) | |
| } | |
| if (current.tile.east != null) | |
| { | |
| remaining.push(new PathNode(current.tile.east, current, current.distance + 1)) | |
| } | |
| if (current.tile.south != null) | |
| { | |
| remaining.push(new PathNode(current.tile.south, current, current.distance + 1)) | |
| } | |
| if (current.tile.west != null) | |
| { | |
| remaining.push(new PathNode(current.tile.west, current, current.distance + 1)) | |
| } | |
| // and put current in seen | |
| checked.push(current); | |
| } | |
| } | |
| // return - note it's tile this time | |
| var ret:Queue<Tile> == new Queue<Tile>(); | |
| // so, we've either found a node or we haven't | |
| // empty is good enough to tell caller there's no answer | |
| // but if it's not empty... | |
| if (finish != null) | |
| { | |
| // we can traverse the path backwards | |
| var current:PathNode) = finish; | |
| ret.push(finish.tile); | |
| while (current.previous != null) | |
| { | |
| push(current.previous.tile); | |
| current = current.previous; | |
| } | |
| } | |
| // tada! The ret queue now has the path in it. | |
| return ret; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment