Avaialble on the iOS App Store here
Given a player position, an opponent position, and a graph representing the maze, this algorithm finds a spot to place an object whose position is pseudo-random and whose shortest-path is also a more or less equal distance to both players.
- Time Complexity: O(E + V), where E is edges and V is verticies in a goven graph
- GKGridGraph is a part of Apple's GameKit API
- graph is used to represent a maze. It's creation and usage is detailed here
- tileManger is a instance of a custom class I made that, in short, allows a bunch of Spritekit nodes to be easily accessed as a grid. Source code is available here.
- playerPosition and opponentPosition are the on-screen coordinates of 2 players
- The Queue data structure used is available here.
- Uses a modified breadth first search to create a minimum spanning tree (a mapping of every node and their distance from a source node) for both players
- These mappings are represented with a 2-D array of verticies and are analyzed to find a node that is:
- Atleast 36 tiles away from each player
- Have a similiar shortest path to each player: ± 7