Instead of a question, I'd like to share my accomplishments
I've asked a lot of questions already and I was feeling almost like I couldn't accomplish anything without receiving explicit help from somebody. Which is actually a pretty fair analysis for the most part. But I've actually accomplished some major stuff which I'm pretty proud of and so I'd like to share some of my code for posterity, and the potential for optimizations from the community (because I think it definitely needs it).
As I've been re-learning how to code, the goal in the back of my mind has been to create a tower defense game, based on a specific concept I thought up years ago and have always wanted to realize. Tower defense games are of course typically built on a 2D grid, with two varieties: some have pre-determined paths, but others provide an open field where the path is determined by the placement of your towers. Which means a pretty lofty challenge: Pathfinding!
I did a lot of reading on google, trying to wrap my head around this problem. Specifically there was a lot about A* and Dijikstra, both of which seemed promising. But, slightly embarrassingly, I couldn't seem to wrap my head around either of them enough to implement them. EVEN with example code. However, I had been sketching out the steps to an A* pathfinding algorithm, as in drawing a grid with a path and seeing how it would play out and even though I couldn't work out the correct implementation, I noticed something.
If you trace the algorithm's path from the starting point, there are usually multiple "identical" tiles. Meaning that the "pathvalue" of the next tiles could be the same, giving you multiple paths instead of the one correct path. Not good. But after sketching it out, I noticed that the reverse isn't true: every tile is given a number based on its distance from the starting point, essentially. And what I realized is that if you start at the ending tile, there is always EXACTLY ONE neighboring tile with a lower number than its own. If you then move to that tile, the same is true again. This takes you on the shortest path all the way back to the starting point.
So basically I ended up with a 3-step process: the first is to examine the current grid and give a number to every accessible tile based on distance from the first tile. The process ends when the finish tile has been found and given a number. The second step is to create a list and put the ending tile in it, then walk backwards to each consecutively lower-scoring tile, adding each one to the list. The final step reverses the list and creates the path properly from start to finish.
I had a couple other smaller issues as well: at first, it only ran correctly if there WAS a solution. So I had to add a failsafe for situations where no path is possible. It also was a one-off process at first: if a path had already been generated, asking it to generate another one was causing it to get stuck in a loop.
Here's an approximation of my solution:
# The following is all contained in my Map(object) class, which defines the grid. # This method goes through EVERY tile and resets ALL relevant values to their initial state, to make sure that the pathfinding method can run. This is where I suspect I could be more efficient, but I haven't come up with a solution yet. def reset_map(self): for y in range(self.numy): for x in range(self.numx): # self.map[y][x] is the coordinates for each tile, which are defined as their own Tile(object) class. Checksum is the value given to them which indicates distance from the start. It defaults to the size of the map in order to be error-proof later. self.map[y][x].checksum = (self.numx * self.numy) self.map[y][x].checked = False # Whether or not the algorithm has visited this tile. self.map[y][x].label.text = "" if self.map[y][x].type == 0: # Type 0 refers to "empty" tiles. This leaves "wall" tiles intact. self.map[y][x].node.fill_color = 'white' # The start and finish tiles look different. More importantly, the start tile needs to be pre-initialized with checksum and checked values or else the algorithm gets angry. self.start.checksum = 0 self.start.checked = True self.start.node.fill_color = 'green' self.finish.node.fill_color = 'red' # This method is the one that does the bulk of the work. def pathfinding(self): # Calls the previous method to make sure all variables are ready. self.reset_map() # This is the list which will hold all tiles which make up the shortest path to the finish. It needs to be empty. del self.pathtofinish[:] # These two lists work in conjunction below to keep track of the next set of tiles to examine and give a checksum value to. Technically it could be done with one list I think? But this was the easiest solution for now. list =  list2 =  list2.append(self.start) # Simple status-checks foundfinish = False trapped = False # Basically... keep processing tiles until you find the finish or have nowhere else to go. while foundfinish == False and trapped == False: # 'list' always contains the latest tiles which were checked. Also known as the "frontier". for i in range(len(list)): # 'list' contains Tile instances, each of which has a method called 'neighbors'. This method identifies all neighboring tiles and failsafes against the boundaries of the grid. neighbors = list[i].neighbors # Loop through all neighbors for the current tile. for j in range(len(neighbors)): # If it's not a wall (1) and it hasn't been checked and the finish hasn't been found yet, process the tile. if not neighbors[j].type == 1 and neighbors[j].checked == False and foundfinish == False: # Every tile gets a checksum value equal to that of its predecessor, then it's marked as checked and added to 'list2', which will contain all tiles which will form the next frontier. neighbors[j].checksum = (list[i].checksum + 1) neighbors[j].checked = True list2.append(neighbors[j]) # Type 3 = the finish tile. After coloring it red, those variable adjustments are all meant to stop all of the current loops immediately instead of hanging. if neighbors[j].type == 3: neighbors[j].node.fill_color = 'red' foundfinish = True j = range(len(neighbors) - 1) i = range(len(list) - 1) # This is where the lists get a little wonky... empty list, transfer list2 to list, then empty list2. del list[:] list = list2[:] del list2[:] # If the list is empty, then we must be trapped (because there's no tiles to check). This will exit the ground-level loop. if len(list) == 0: trapped = True # If we AREN'T trapped, then it's safe to generate a path! if trapped == False: self.generate_path() # Pretty self-explanatory really.... def generate_path(self): # We only need to look at one tile at a time, starting with the finish tile. Add it to the pathtofinish list. current = self.finish self.pathtofinish.append(self.finish) # We're going to run this process for as many steps as there are tiles in the shortest path. for i in range(self.finish.checksum): # Maybe not the best, but j is used as a "fake" loop, incremented at the end of the while loop. j = 0 nextfound = False # Loop until the next tile in the path has been found. It will ALWAYS find a tile so it's safe. while nextfound == False: # We'll examine each neighboring tile one at a time. selected = current.neighbors[j] # If the selected tile has a lower value then the current one, then it's part of the shortest path. if selected.checksum < current.checksum: # Append it to the pathtofinish list, make it the next current tile, rinse and repeat. self.pathtofinish.append(selected) current = selected nextfound = True j += 1 # Reverse the list for easier use later, then draw the path (pretty simple). self.pathtofinish.reverse() self.draw_path()
That's the gist of it. A bit messy but 100% functional. It has all necessary failsafes, and it has SOME optimizations, for example it only searches the grid until it comes across the finish then it leaves the rest of the tiles unexplored. Unfortunately though, the current implementation means that it has to look at EVERY SINGLE TILE at LEAST once for the resetting of the map, then it looks at MOST of the map for the pathfinding method.
I'm actually not sure if my final solution is similar to the A* algorithm, since it was initially based off of that before I figured something out on my own. And I'd love to optimize it because every time a wall is placed, it runs through the entire process from resetting to drawing and while it's not bad (I'd say well under half of a second), it's noticeable if you're tapping quickly.
Anyway, thanks for reading. I'll gladly answer any questions!
Good work @WTFruit
It's always satisfying to crack a tough challenge!
I don't have any experience of pathfinding algorithms but I'll have a closer look at your code.
Do you have other code to include this class in to see it in action?
I don't either :) obviously it's a solved problem and I learned that there's several ones, including some which mix the basic algorithm with "greedy" tendencies, which can find the solution quicker depending on the scenario. I'm not 100% sure how to build that into MY solution.
I think tomorrow evening I will have enough time to put together and share a more complete example of my stuff, I didn't include everything right here partially because it's just a lot in order to get a complete running example, and partially because it's VERY sloppy at the moment and hard to read.
Just as a brief description though, here's the overhead I am (was) dealing with, causing lag with every touch event:
Every touch event triggered a non-abbreviated loop through EVERY tile, to find the one whose boundaries contain the touch. I currently have a total of 264 tiles so that's a fairly lengthy list.
The touched tile flips its state to either 'wall' or 'empty'. After that, the 'reset' process looped through the ENTIRE grid again, to reset every single one to a clean state. So 264 more steps.
The initial pathfinding algorithm is currently highly variable. It IS set up to stop looping as soon as it reaches the exit, but this means that a longer path will result in more steps. Not only that though, it simply spreads out from the starting point which means that a more open grid (few walls) results in it actually searching through the ENTIRE grid again. If the entrance and exit are on exact opposite ends of the map and there's no significant walls, that's LITERALLY what happens. So potentially 264 more cycles to go through.
Here it gets better. Walking back from the exit to the entrance is almost as efficient as possible: it moves to each tile, and examines its neighbors one at a time until it finds the one with a lower checksum value. So it can potentially get maybe up to about 100 tiles checked but in a lot of situations will be lower.
The final step is the easiest: it walks back FORWARD through the path, and knows exactly where to go so there's no searching. This step technically can probably be eliminated after I'm done debugging but for now it's nice to have.
This is just spitballing, but on the high end that means looking at tiles about 900 times from the time you touch the screen until the time it finishes the entire process. This results in a visual lag.
I'll quickly share though that I made a couple of optimizations, though not in the pathfinding algorithm itself:
In order to find out which tile was tapped, I replaced the gridsearch (264 cycles) with some math since it's a predictable situation really.
Instead of resetting EVERY tile, the algorithm makes a list and adds every modified tile to it. The reset_map() method simply resets the tiles in that list. This doesn't help a TON (it doesn't help for the largest searches that I mentioned) but if the path was quick to find, the next time it resets the map it'll be very brief.
Sorry, it took me a little while and I had to decide how to upload it. It's a handful of scripts and (currently) one asset so it's all in a google drive folder:
Just download the entire contents of the folder and keep the structure the same, since the code references the image in the assets folder.
Let me know if you have any problems!
EDIT: Some details I forgot!!
Since I'm doing this in xcode, I modified some settings which might create weird results if you port the code INTO Pythonista... I hid the statusbar, forced landscape orientation, and disabled multi-touch.
Thanks! I'll check it out.
Fwiw, this is basically Dijkstra's algorithm. I'll explain it to you tomorrow. It's pretty similar.
After re-reading some material on A* and Dijikstra I see that you're right and I misspoke. The sketching that I did on a piece of paper was the start of Dijikstra, like you said. If you have the time, I'd love clarity on the subject in general because once again, a lot of what I'm reading is going over my head as far as how to implement them. As far as the algorithm is concerned, it looks like I'd be better served by either A* or by Dijikstra with a priority queue. The latter is what I tried and failed to create on my own for awhile.
Sure. I did Dijkstra in https://github.com/controversial/maze-cv/blob/master/pathfinding/dijkstra.py.
So to begin, you need to understand the concept of a graph. The graph is the entire thing you're trying to find a path through. It's made up of "nodes" and "edges." A node represents a single point in space. For maze-cv, the nodes were all the white squares on the graph. An edge is simply a connection between two nodes, and it has a length, representing how far apart the nodes are. In maze-cv, there was an edge with length 1 between each adjacent square.
Another good example is an application like Google Maps. For this kind of program, the nodes would be each intersection between two roads, and then the edges would be the roads themselves, cut up into sections between intersections. The length of an edge would be the distance along a road between two intersections.
So basically, Dijkstra is like a flood fill with a bit of added logic to track the "parent" of each node. In a flood fill, you start at one node and recursively explore adjacent nodes until you've covered them all. To get Dijkstra, we just have to assign parents to each node so we can trace the route back to the start once we reach the end.
I understood the basic concept, although I think it's easier in my mind when it's varying edge lengths rather than the uniformity of a grid for some reason. In any case, I pretty clearly managed that part just fine.
It's the ending where I think my implementation differs SLIGHTLY, even though the result is the same. Heck, maybe even the ending is the same since I do have to backtrack to create the path, like you mentioned.
Ok. Well for the rest: as you explore, you track the distance along edges that it took you to get to each node. For example, if we take a path to get to a node along an edge with distance 4 and an edge with distance 3, the distance would be 7. This is necessary to find the shortest path. So imagine we have two paths to a node. Along one path, the distance is 7. But say we come back later and the distance is only 4! If this is the case, we change the node's distance to 4 and readjust the parents. In this way, when we trace a path back, that path is always the shortest, because we explore all possible paths and always pick the shortest one we find.