Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... It is old, but you once again made me take notes and added one more thing to mess with to my list of things to do. Thank you. I do appreciate the effort you've put in and the information you presented. URL: https://forum.audiogames.net/post/513786/#p513786 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... O hah. This is really old. Nevermind. Still good info in my previous post. URL: https://forum.audiogames.net/post/513672/#p513672 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... So, the algorithmic complexity of A* is exponential, which this topic has already discovered. But:If you code Astar right, you have several callbacks: one for determining next possible actions given coordinates, one for determining how close coordinates are to the goal (usually called the heuristic), and one for determining if some coordinates are the goal. I suspect you've coded it with a specific implementation that doesn't use callbacks at all, so find the places in your code that match up to this and you can do some of the same things (but an implementation with callbacks is useful because it can pathfind over things like combo chains, and other stuff that's not space). Unfortunately if you're coding Astar yourself it's hard to prove it works and you probably didn't go general enough for the good optimizations to be easy, but the things you want to do are as follows.First thing to optimize Astar is make the goal more lenient: "within 5 units of the player", "there is a straight line to the player", etc. Give it more options to play with.Second thing with Astar: limit the maximum length of the path. It will try all possible paths, but you can stop it at all path lengths of 10 say, and then it will only consider paths less than 10. This will eliminate the worst case of "no path" at the cost of sometimes not finding a path when there is one. Except that not finding a path when there is one makes better gameplay, since realistically nothing's going to go 200 units all over to try to get to you.Third, you can stop Astar as soon as it's found any path whatsoever, rather than letting the algorithm complete to find the shortest.Fourth, refactor the pathfinding to be in a class, which will let you tick the class. Then instead of running it all at once, modify the main loop of it to store data in the class instead of on locals, then you can run 1000 iterations per game tick. Paths won't be instantly available, but no matter how long they take, the game won't lag. Even if you get pathfinding to 0.1 sec this is still a good idea, since 0.1 sec times 10 enemies is a whole second.Fifth, you can optimize the estimation of how close a tile is to the goal. Usually people start with pythagorean distance, that is sqrt((c.x-goal.x)**2+(c.y-goal.y)**2), but this is expensive in any programming language: instead, if players can only move horizontally and vertically, Manhattan distance can also work while being faster: abs(c.x-goal.x)+abs(c.y-goal.y), which is the minimum amount of distance on the best path if the player can't move at angles. Surprisingly, this heuristic (and a wide variety of other heuristics) can work even when they don't hold true, since it's just an estimate, and doesn't need to be fully accurate.Sixth, the way Astar works (formally speaking) is via a cost function, c(x)=f(x)+h(x), where f(x) is the length of the path so far, and h(x) is the estimation to get to the goal from the end of path x. You can rewrite this as c(x)=(1-w)*f(x)+w*h(x), which gives you a tunable parameter: w=0 is bredth-first search, w=0.5 is Astar, and w=1 is best-first search. This is kind of esoteric, but the thing is that for most games if you say that you'll take the first path and you also set w=0.9 or w=1, you'll start getting really fast pathfinding. This surprisingly works on not games too: the reason I know so much about this is that there was a month-long Astar project in college, and this was part of the experimentation I did on something much larger.Seventh, if the player is going to commonly do things like jump up on platforms, and this immediately makes them unreachable, pathfind from the player to the enemy instead of from the enemy to the player. This will make Astar give up faster, if the paths it tries from the player are really short because of the edge of a platform.Finally, consider optimizing your data structures. If you're using Python lists everywhere, you're getting a lot of slowness from sorting and things that you could be avoiding if you find a proper ordered set on Pypi, etc.And once you've done all that, Cython does indeed compile 100% normal Python files for the most part, so you can run it through Cython for even more speed in a lot of cases.But don't think pathfinding has to be Astar. There are better algorithms depending on what you're doing. One I particularly like is from the roguelike people: maintain a second tile map of integers, all starting at 0. Then, every tick, increment the tile where the player is standing by 1, and run a loop over it which floodfills by decrementing tiles greater than zero. This is kinda hard to articulate but pretty easy to code, and it's realistic: enemies just always walk toward the tile with the highest number. And you get all sorts of emergent stuff out of it
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Misspost, i'm so sorry I posted in wrong topic. Please ignore that. URL: https://forum.audiogames.net/post/513631/#p513631 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Thank you for that save URL: https://forum.audiogames.net/post/513629/#p513629 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Certainly it is confusing.What I mean is converting as many Python functions and types into C types as possible, and when you compile, Cython generates pure C code that doesn't interact with the much slower CPython API during the actual operation.My Pathfinder has a pathfinder class like this.# distutils: language=c++ // I'm using C++ so I can use a vector, which is basically a list who's members must all have the same type. Much faster than a Python list.from libcpp.vector cimport vectorcdef struct location: // A C struct is sort of like a Python class. They can't have methods, and you can only store C types. This struct, location, just has 2 properties, x and y, which represent the location of a single tile on a map. unsigned short x, y // Unsigned short, like in BGT, is 2 bytes, and can be from 0 to 65535cdef struct square: // The pathfinder allocates and stores one of these for every square on the map. char terrain // A 1 byte number, -128 to 127. A value less than 0 means this square is impassable. 0 means there is no cost, and every value above 0 increases the cost to walk there. location parent, loc // Parent is the square that the pathfinder was previously on, loc is the coordinates of this tile. unsigned short factor // Internal number bint closed // bint is bool, true means this square is closed and should not be looked at anymore.cdef class pathfinder: # Cdef declares a C class, which can store C datatypes and can take up less memory. cdef: # Declare all the properties stored in each pathfinder in a cdef block vector[vector[square]] map # This is a list, each item of which is a list of square structs representinng a square on the map. So while pathfinding, you can get a tile by doing self.map[x][y] readonly unsigned short max_x, max_y # Readonly means that you can see the values from outside Cython code, but you can't change them. def __cinit__(self, unsigned short max_x, unsigned short max_y): # This function prepares the internal map, the max_x and max_y parameters are the size of the map. cdef vector[square] k cdef coord i, j cdef square sq self.map.reserve(max_x) for i in range(max_x): k.clear() // Make sure it's empty. k.reserve(max_y) // Allocate exactly enough memoy in this list for max_y squares. for j in range(max_y): sq=square(parent=location(0, 0), closed=0, terrain=0, loc=location(i, j), factor=0) // Create a new square k.push_back(sq) // And add it to the vector of squares that we're preparing... self.map.push_back(k) # and Now we have a vector of squares that we push onto the map. self.max_x=max_x self.max_y=max_y def __dealloc__(self): # __dealloc__ is like __del__, but you should not touch Python objects stored in self. Here, we deallocate the map and free a lot of memory. cdef vector[square] i for i in self.map: i.clear() self.map.clear() # We iterate through self.map, which of course is a list of vectors, then we clear each vector.Then, we clear self.map its self.This should give you an idea of what is required.You can try reading the Cython tutorials and also the user guide at cython.org.HTH URL: https://forum.audiogames.net/post/498556/#p498556 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... A quick update:I have found a pretty good tutorial here which gives very detailed instructions on what to do. Anyone looking to start with Cython should start here. URL: https://forum.audiogames.net/post/498555/#p498555 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Mind linking to some tutorials you found helpful? I have a working algorithm, that is for sure, so I wouldn’t mind converting it, as long as I can get clear instructions on how to do so. Everything I found was really confusing. I also need a way to pass in a function as a parameter for a callback, as my pathfinder does not technically have a map. It has a function which is called with new coordinates and works with that function output. URL: https://forum.audiogames.net/post/498409/#p498409 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Mind linking to some tutorials you found helpful? I have a working algorithm, that is for sure, so I wouldn’t mind converting it, as long as I can get clear instructions on how to do so. Everything I found was really confusing. I also need a way to pass in a function as a parameter for a callback, as my pathfinder does not technically have a map. It has a function which is called with new coordinates and works with that function input. URL: https://forum.audiogames.net/post/498409/#p498409 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... Mind linking to some tutorials you found helpful? I have a working algorithm, that is for sure, so I wouldn’t mind converting it, as long as I can get clear instructions on how to do so. Everything I found was really confusing. I also need a way to pass and function as a parameter for a callback, as my pathfinder does not technically have a map. It has a function which is called with new coordinates and works with that function input. URL: https://forum.audiogames.net/post/498409/#p498409 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... You could write your Pathfinder in optimized Cython.I wrote a simple AStar pathfinder this way and the speed is extreme.I'm only 96% sure it always works though. URL: https://forum.audiogames.net/post/498356/#p498356 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... @2, thank you.I did both, put a hard limit on the amount of nodes there can be in either open or closed lists (500 I think), and I reduced the region calculation to 10 units. It doesn't lag now, and even if it fails to find a path the time it takes to tell me so is under 0.1 second. I've got another problem now, but I think I can tinker with it and figure it out. Long story short, if an enemy is at 20 0 and I am at 0 11, it will try to look for a path to 9 11 (attempting to match the region I am in on both the x and the y axes). Still, at some point I gotta move on, and I am quite happy with what I already have for pathfinding. URL: https://forum.audiogames.net/post/498303/#p498303 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Re: Pathfinding working... sort of...
Re: Pathfinding working... sort of... The reason its probably freaking out is because it can't find a path, so tries every possible permutation to get there. You could put in a cutoff for how long its epected to go for without reaching a path, but that could effect its ability to pathfind some distances. You could also do an initial check to see of the player tile is reachable, if not scan around the player, or close enough to the player, for a tile that is, and path to that, such as a tile just below the cliff edge. As for speeding it up across regions, sectorize more and path incrementally. Instead of charting a path directly from 0 to 200, chart one from 0 to 10, and when it reaches 10, path from 10 to 20, and so forth and so on. URL: https://forum.audiogames.net/post/497908/#p497908 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
Pathfinding working... sort of...
Pathfinding working... sort of... As the topic title suggests, I have managed to get Pathfinding to work. I have even managed to split the map into regions (though only regards to pathfinder and enemies... everything else treats it as a single block). My problem? Astar, which is what I used to search, takes too long to find paths that do not exist.I shall provide an example to illustrate my point.Suppose that the player is at 0 0. Also suppose that the enemy is at 300 0. Finally, keep in mind that there is nothing between the player and the enemy besides empty street through which both can walk and eventually encounter one another.Step 1:Enemy scans its surroundings and sees that the player is somewhere to the left within it's regions.Step 2: Enemy scans for the best path to the next region over and sees that the best path is to 299, the beginning of the region to the left.Step 3: The enemy takes a step to repeat steps 1-3, as it is now in the new region. It does so twice, once to obtain the path to 199 0, and once more to obtain the path to 99 0, the region in which the player resides. Only then does it directly scan for the player by using their coordinates.That works beautifully, no complaints or anything. It is even under 0.02 seconds, which is going to help a lot when some of enemy's friends decide to pay the visit to the map.However, what if the player was out of reach?Allow me to provide you with another example:The player is now at 5 5, do to them managing to skillfully propel themselves onto a platform via using their legs. There is no connection to the ground what so ever, leaving the enemies unable to reach him. The enemy is still at 300 0.Steps 1 - 3 execute once again, until the enemy reaches 99 0 (the player's region). Here is where things become... difficult.The Astar, which was performing at 0.02 second when the path actually existed, now takes anywhere between 4.1 and 4.5 seconds to scan through every route, giving up in the end because I have not implemented jumping.The question is... why such a large increase in time? How would I go about reducing it to a more reasonable level? What else besides regions could I add in order to reduce the time required to scan through the map? Would reducing the region size help?I am pretty sure my implementation of AStar is fine (I looked up how others did it and improved mine as I've learned). URL: https://forum.audiogames.net/post/497891/#p497891 -- Audiogames-reflector mailing list Audiogames-reflector@sabahattin-gucukoglu.com https://sabahattin-gucukoglu.com/cgi-bin/mailman/listinfo/audiogames-reflector
