• WTFruit

    @Webmaster4o

    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.

    posted in Pythonista read more
  • WTFruit

    @Webmaster4o

    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.

    posted in Pythonista read more
  • WTFruit

    @chriswilson

    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:

    https://drive.google.com/folderview?id=0B5-adIslOLy_QUZsUDRwREhOTkk&usp=sharing

    Just download the entire contents of the folder and keep the structure the same, since the code references the image in the assets folder.

    main.py contains all the scene code, button.py and color.py are a couple things I threw together, and gameobjects.py is for all the gamecode not located in the scenes.

    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.

    posted in Pythonista read more
  • WTFruit

    @chriswilson

    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:

    1. 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.

    2. 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.

    3. 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.

    4. 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.

    5. 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:

    1. 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.

    2. 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.

    posted in Pythonista read more
  • WTFruit

    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!

    posted in Pythonista read more
  • WTFruit

    @ dgelessus

    Good point, I was focused on solving the perceived problem and didn't even think about that. However, what would happen in the case of a hypothetical crash? Is there any way for it to ever "unintentionally" land on the debugging console?

    posted in Pythonista read more
  • WTFruit

    So I've been having a ton of fun doing all my work in xcode now and running in the simulator, and just now I started sideloading onto my phone as well. It's great. I even figured out how to force landscape and hide the statusbar as well so I've been pretty happy!

    The one thing is... I can't figure out any way to eliminate the console which appears after the app is closed. Currently I close my final scene with

    mainview.close()
    

    Which, again, quits the app but presents the debugging console. What are my options?

    posted in Pythonista read more
  • WTFruit

    @dgelessus

    My indentation has been very consistent (only using tab) but I think I figured it out sort of. I neglected to mention that I actually got my project up and running in X-Code and I'm pretty sure that's what was causing trouble. I messed with the "intelligent indenting" preferences a little bit and the problem hasn't come back so far.

    posted in Pythonista read more
  • WTFruit

    @omz

    I would assume user-error for now on my earlier attempts... Lord knows I make enough of them!

    I know I'm cross-threading now but interestingly, I've had another error go away: when I asked about the modal_scene issue, and the last comment I made was that I got it to work but it was still throwing the same error into the console at the same time. Well, as I kept working that just randomly stopped eventually. I was adding things (more nodes and tweaking things) to the modal scene so based on your original comment that's likely related I suppose?

    EDIT: on the subject of bugs, I'm assuming this is one: I have a codebase that works 100% fine at the moment, but when I try adding a new method to one of my classes it's throwing me an indentation error. I made it as simple as possible so there's nothing I could have screwed up... it's the most basic method I could create, it contains one print comment, I'm not calling it anywhere, I added the colon at the end of the definition... but it gives me the indentation error. Comment out those two lines of code though and it runs like a charm again.

    posted in Pythonista read more
  • WTFruit

    @Phuket2

    Again, I'm still learning (hence all the questions I keep asking), but I've been basically focusing all my energy on doing stuff with scenes so please feel free to hit me up if you have any questions.

    posted in Pythonista read more

Internal error.

Oops! Looks like something went wrong!