• 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
  • WTFruit

    @Phuket2 ,

    Since I'm easily the inexperienced one here take what I say with a grain of salt but since I've been staring at the documentation 24/7, I think what you're asking for is explicitly mentioned as a useful possibility. In fact, here it is from the scene module documentation:

    "Integration with the ui Module
    The easiest way to run a scene is to use the run() function, which presents the scene in full-screen. Sometimes this is not what you want, especially if the scene you’re building is not actually a game. For more flexibility, you can also create a SceneView explicitly, set its scene attribute to the scene you want to present, and then add it to a view hierarchy that you created using the ui module.

    You can also use this approach to add traditional UI elements (e.g. text fields) to your game. For this purpose, you don’t have to create a SceneView – you can simply use the view that was created automatically, using your Scene‘s view attribute (this will only work if a scene is already being presented of course).

    The ui module can also be useful for rendering vector images (shapes, text etc.) that you want to use as textures. A Texture can be initialized from a ui.Image for this purpose, typically one that you create using an ui.ImageContext. The ShapeNode and LabelNode classes use this approach to render their content."

    Ignore me if I'm just spouting useless stuff but your comment caught my eye!


    @chriswilson ,

    Interestingly, your example (even with modifications to fit how I write), actually did the job perfectly. I even removed the parentheses from the tuplet (as I've been doing by habit for a little while already) and it still worked.

    Even more interestingly, I tried it in my program one more time and it actually worked this time. Literally the same exact line: self.node.size = w, h. Weird stuff!

    Also, it completely distorted it just like your predicted which means that despite all of this, it will probably be best to redo the path anyway like you said.

    posted in Pythonista read more
  • WTFruit

    @Phuket2
    @chriswilson

    Thank you both of you for responding! I can't stop asking questions but I've been feeling so bad that omz answers every time!

    A couple things:

    1. The following did not have any effect:
    Self.node.size = (width, height)
    

    And I think I mentioned it but I've been trying to find a different variable or method to call without any luck.

    1. The following DID work:
    self.node.path = ui.Path.rounded_rect(x, y, w, h, r)
    

    However, would it be possible to eliminate all parameters except for width and height, and even eliminate the reference to the type of shape? Of course I can pass through the previous parameters and I can run a check to see if a given Shapenode object is a rect or rounded rect but all of that seems like a runaround solution if I could just access the path's dimensions directly.

    posted in Pythonista read more
  • WTFruit

    I've scoured the scene module trying to find an option other than deleting the node and replacing it with an updated one which seems excessive.

    If I want to update a node's position (without animation) I can simply write:

    self.node.position = x, y
    

    But if I try using self.node.size in a similar way, nothing happens. The values update (I checked with a print command) but visually nothing changes.

    I imagine this has to do with the involvement of a ui.Path object to create the Shapenode in the first place but I'm not sure what to do with that potential fact. What's the most straightforward way to update a Shapenode's dimensions?

    posted in Pythonista read more
  • WTFruit

    @omz

    Huh okay! Very small detail that I would have missed but makes sense now. Thanks :)

    posted in Pythonista read more
  • WTFruit

    @omz

    I can't get A.call() working :/ I get the error "Object is not callable". The offending line is:

    A.call(self.method())
    

    Where A = scene.Action.

    posted in Pythonista read more
  • WTFruit

    @omz (or anyone else reading this)

    I finally got an implementation of the modal_scene working (took me long enough), it brings up the modal scene and everything. But it still gives me the same initial error at the moment that the modal scene is called. Is there anything I can do about that?

    Thank you for the scene-change code by the way, it works like a charm. Although I was curious why this works:

    self.menu = Scene2()
    self.present_modal_scene(self.menu)
    

    But not this:

    self.present_modal_scene(Scene2())
    

    I guess I'm misunderstanding the use of self.menu, I assumed it was basically a pointer, a stand-in for the other phrasing of the code (Scene2()).

    posted in Pythonista read more
  • WTFruit

    @omz

    Hmmm interesting! I'll try that out shortly then. Any advice on multiple "main" scenes and how to more properly switch between them?

    posted in Pythonista read more
  • WTFruit

    @omz

    Fair point that I never thought of, but I removed those without any change. Same error :/

    posted in Pythonista read more
  • WTFruit

    I do feel bad, I don't want to be nagging but since there aren't 3rd-party resources for most of my questions, and I'm occasionally bumping into problems that I can't seem to figure out, I don't think I have anywhere else to go.

    I'm trying to work out multiple-scene situations now. I thought the first possibility sounded very easy to implement: use present_modal_scene to display a scene on top of the original one. Unfortunately, even though everything looks right to me and I'm doing it exactly the same way as the example games (as far as I can tell), I'm getting an error.

    Secondarily, I don't see an elegant way to move between scenes. Currently I have noticed that I can create another scene and run it whenever I want but it just puts it on top of the previous one, which is still running in the background and when I hit the "x", it takes me to the original scene. That doesn't seem like an ideal outcome.

    So, the first problem. Here's my modal scene code:

    import scene
    import ui
    
    class Scene1(scene.Scene):
    
       def __init__(self):
          pass
    
       def touch_began(self, touch):
          self.menu = Scene2()
          self.present_modal_scene(self.menu)
    
    
    class Scene2(scene.Scene):
    
       def __init__(self):
          pass
    
    
    scene.run(Scene1())
    

    When I run that code it starts fine but when I tap to bring up the second scene, I get this error:

    ValueError: max() arg is an empty sequence

    I'm very stumped. I feel like it couldn't be a simpler thing but I've hit a wall.

    The second problem (the general ability to switch between scenes), I don't even know where to begin with because I can't find any examples or info in the documentation.

    Sorry for asking so many questions!

    posted in Pythonista read more
  • WTFruit

    @omz

    Hmm. I did try that and had gotten an error, but if you think it should work I'll try it a bit more :). Thanks!

    posted in Pythonista read more
Internal error.

Oops! Looks like something went wrong!