Re: [pygame] Pathfinding
On Wed, Jan 28, 2009 at 4:09 PM, Yanom Mobis ya...@rocketmail.com wrote: ... I'm just going to make my game tile-based, I guess. Just a tip: you can have tile-based pathfinding without tile based graphics. And the tiles don't necessarily have to be the same size as you might think of when you think tile. It depends on how tightly your game is packed, but if it is mostly wide open spaces, you could have large tiles for pathfinding | | RR | | n | RR | | |RR| | | | | | | | | | If the n needs to go somewhere in the lower right, he can't go through the tile with the big rock. If you have very tightly packed levels, you need finer tiles. If you have a mix, the tiles could be hierarchial, where pathfinding from far distances first use the larger tiled map, but pathfinding within one of those large tiles uses a higher resolution tilemap. You can also have normal sized tiles for pathfinding. But the method used for pathfinding does not need to correspond with the method you use for graphics. Brian, I really like that method based on vision tests! I'm going to try it out next time I have a game that needs something like that.
Re: [pygame] Pathfinding
so I make a tile-based game, then trick the player into believing it's not tile-based? --- On Thu, 1/29/09, Patrick Mullen saluk64...@gmail.com wrote: From: Patrick Mullen saluk64...@gmail.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Thursday, January 29, 2009, 12:57 PM On Wed, Jan 28, 2009 at 4:09 PM, Yanom Mobis ya...@rocketmail.com wrote: ... I'm just going to make my game tile-based, I guess. Just a tip: you can have tile-based pathfinding without tile based graphics. And the tiles don't necessarily have to be the same size as you might think of when you think tile. It depends on how tightly your game is packed, but if it is mostly wide open spaces, you could have large tiles for pathfinding | | RR | | n | R R | | | RR | | | | | | | | | | If the n needs to go somewhere in the lower right, he can't go through the tile with the big rock. If you have very tightly packed levels, you need finer tiles. If you have a mix, the tiles could be hierarchial, where pathfinding from far distances first use the larger tiled map, but pathfinding within one of those large tiles uses a higher resolution tilemap. You can also have normal sized tiles for pathfinding. But the method used for pathfinding does not need to correspond with the method you use for graphics. Brian, I really like that method based on vision tests! I'm going to try it out next time I have a game that needs something like that.
Re: [pygame] Pathfinding
Any 2D space can be divided into tiles, even if it is not really made of tiles. So maybe a better way of looking at it is to make a non-tile-based game and trick the pathfinding code into believing it is tile-based. --- James Paige On Thu, Jan 29, 2009 at 02:42:56PM -0800, Yanom Mobis wrote: so I make a tile-based game, then trick the player into believing it's not tile-based? --- On Thu, 1/29/09, Patrick Mullen saluk64...@gmail.com wrote: From: Patrick Mullen saluk64...@gmail.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Thursday, January 29, 2009, 12:57 PM On Wed, Jan 28, 2009 at 4:09 PM, Yanom Mobis ya...@rocketmail.com wrote: ... I'm just going to make my game tile-based, I guess. Just a tip: you can have tile-based pathfinding without tile based graphics. And the tiles don't necessarily have to be the same size as you might think of when you think tile. It depends on how tightly your game is packed, but if it is mostly wide open spaces, you could have large tiles for pathfinding | | RR | | n | RR | | |RR| | | | | | | | | | If the n needs to go somewhere in the lower right, he can't go through the tile with the big rock. If you have very tightly packed levels, you need finer tiles. If you have a mix, the tiles could be hierarchial, where pathfinding from far distances first use the larger tiled map, but pathfinding within one of those large tiles uses a higher resolution tilemap. You can also have normal sized tiles for pathfinding. But the method used for pathfinding does not need to correspond with the method you use for graphics. Brian, I really like that method based on vision tests! I'm going to try it out next time I have a game that needs something like that.
Re: [pygame] Pathfinding
oh --- On Thu, 1/29/09, James Paige b...@hamsterrepublic.com wrote: From: James Paige b...@hamsterrepublic.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Thursday, January 29, 2009, 5:00 PM -Inline Attachment Follows- Any 2D space can be divided into tiles, even if it is not really made of tiles. So maybe a better way of looking at it is to make a non-tile-based game and trick the pathfinding code into believing it is tile-based. --- James Paige On Thu, Jan 29, 2009 at 02:42:56PM -0800, Yanom Mobis wrote: so I make a tile-based game, then trick the player into believing it's not tile-based? --- On Thu, 1/29/09, Patrick Mullen saluk64...@gmail.com wrote: From: Patrick Mullen saluk64...@gmail.com Subject: Re: [pygame] Pathfinding To: pygame-us...@seul.org Date: Thursday, January 29, 2009, 12:57 PM On Wed, Jan 28, 2009 at 4:09 PM, Yanom Mobis ya...@rocketmail..com wrote: ... I'm just going to make my game tile-based, I guess. Just a tip: you can have tile-based pathfinding without tile based graphics. And the tiles don't necessarily have to be the same size as you might think of when you think tile. It depends on how tightly your game is packed, but if it is mostly wide open spaces, you could have large tiles for pathfinding | | RR | | n | R R | | | RR | | | | | | | | | | If the n needs to go somewhere in the lower right, he can't go through the tile with the big rock. If you have very tightly packed levels, you need finer tiles. If you have a mix, the tiles could be hierarchial, where pathfinding from far distances first use the larger tiled map, but pathfinding within one of those large tiles uses a higher resolution tilemap. You can also have normal sized tiles for pathfinding. But the method used for pathfinding does not need to correspond with the method you use for graphics. Brian, I really like that method based on vision tests! I'm going to try it out next time I have a game that needs something like that.
Re: [pygame] Pathfinding
Yanom Mobis wrote: ok, i didn't get any of that There's a mask module in pygame with a Mask class that contains one bit per pixel. It's not in the online docs yet, but in svn head there's a method called convolve that takes in another Mask. If you start with a Mask (lets call it map) which has the corresponding bit set if there's an obstacle there, and another Mask (call it player) which has the shape of your player, then map.convolve(player) will have the (x,y) bit set if the player can be moved to (x,y). Then you can do your pathfinding in that mask with A* or whatever, and the resulting path will be one where the player never touches an obstacle. If your map is small, this will be feasible, but if it's large then building and searching a pixel-based map of the whole area will possibly take too long and you'd need to do something smarter. --Mike
Re: [pygame] Pathfinding
I'm just going to make my game tile-based, I guess. --- On Wed, 1/28/09, Michael George mdgeo...@cs.cornell.edu wrote: From: Michael George mdgeo...@cs.cornell.edu Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Wednesday, January 28, 2009, 8:41 AM Yanom Mobis wrote: ok, i didn't get any of that There's a mask module in pygame with a Mask class that contains one bit per pixel. It's not in the online docs yet, but in svn head there's a method called convolve that takes in another Mask. If you start with a Mask (lets call it map) which has the corresponding bit set if there's an obstacle there, and another Mask (call it player) which has the shape of your player, then map.convolve(player) will have the (x,y) bit set if the player can be moved to (x,y). Then you can do your pathfinding in that mask with A* or whatever, and the resulting path will be one where the player never touches an obstacle. If your map is small, this will be feasible, but if it's large then building and searching a pixel-based map of the whole area will possibly take too long and you'd need to do something smarter. --Mike
Re: [pygame] Pathfinding
Here's a tutorial of pathfinding with A*, specifically for PyGame: http://eli.thegreenplace.net/2009/01/09/writing-a-game-in-python-with-pygame-part-iii/ On Mon, Jan 26, 2009 at 19:01, Michael George mdgeo...@cs.cornell.eduwrote: Marius Gedminas wrote: My personal snag with A* is that the NPCs seem to know too much about the map and directly walk the most optimal path without exploration. One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. This could probably be implemented fairly cleverly by using generators. You'd probably have to experiment with different algorithms to find a more realistic approach - I suspect that A* would involve lots of wandering since it assumes constant access time for all known branches (whereas the character has to walk up and down the tree). DFS would probably be more realistic. --Mike
Re: [pygame] Pathfinding
is it easier to make the game tile-based? if I make every pixel a node, and there are 2 obstacles really close together, how will I make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening? --- On Mon, 1/26/09, Jake b ninmonk...@gmail.com wrote: From: Jake b ninmonk...@gmail.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 10:43 PM Have you played any of the unreal tournament games? The way it pathfinds is like what you're asking. It uses a graph ( a bunch of nodes connecting to each other. It actually pre-calculates pathfinding, but you don't need to worry about that at first ) The link posted has a good image: http://en.wikipedia.org/wiki/Graph_%28mathematics%29 ( look at the first one ) Looking at the image, image 1 = health,l 2=flak gun, 3 = ammo, 5 = flag, etc... If a bot wants to go from 3 to 5, you can use A* to find the path. It just needs a graph ( a bunch of nodes, which can connect to other nodes ) The actual (x,y,z) location of the nodes doesn't matter. ( But if the distance is too far, you need to take that into account by the weight, or, add a node between them ) On Mon, Jan 26, 2009 at 7:11 PM, Yanom Mobis ya...@rocketmail.com wrote: a graph, as in just a regular x, y kind of thing? I don't need an overly complex library, is something less complex available? You can use a regular list-type of tiles. And each list item holds a list of pointers to all tiles that it connects to. If you are doing a tile based map, using a 2D array could simplify things. ( using numPy ) # this is a bad example, but, to give you an idea: class Tile(): def __init__(self): self.clist = [] t1 = Tile() t2 = Tile() t3 = Tile() # 1 connects to 2 and 3 t1.clist.append( t2 ) t1.clist.append( t3 ) # 2 connects to 1 t2.clist.append( t1 ) # 3 connects to 1 t3.clist.append( t1 ) # map a list of Tile()s map = [t1, t2, t3] -- Jake
Re: [pygame] Pathfinding
Yanom Mobis wrote: is it easier to make the game tile-based? if I make every pixel a node, and there are 2 obstacles really close together, how will I make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening? One possibility is to use the new convolution code in the mask module - if you convolve the obstacles with the shape of the object that's moving, you can do pathfinding in the resulting mask and it will only move where it fits. Depending on your situation, this might be a reasonable approach. --Mike
Re: [pygame] Pathfinding
ok, i didn't get any of that --- On Tue, 1/27/09, Michael George mdgeo...@cs.cornell.edu wrote: From: Michael George mdgeo...@cs.cornell.edu Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Tuesday, January 27, 2009, 4:38 PM Yanom Mobis wrote: is it easier to make the game tile-based? if I make every pixel a node, and there are 2 obstacles really close together, how will I make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening? One possibility is to use the new convolution code in the mask module - if you convolve the obstacles with the shape of the object that's moving, you can do pathfinding in the resulting mask and it will only move where it fits. Depending on your situation, this might be a reasonable approach. --Mike
Re: [pygame] Pathfinding
On Jan 27, 2009, at 3:36 PM, Yanom Mobis wrote: is it easier to make the game tile-based? Probably, but it really depends on the details. if I make every pixel a node, and there are 2 obstacles really close together, how will I make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening? If this is a 3D game, what does a pixel mean? ;^) This could be done by vetting candidate routes using collision detection. Assuming you can reduce the path into a series of straight lines, you could create a rectangular prism with its height and depth set to the size of the bounding rectangle of the frontal area of the thing you are moving and it's length set to the distance of the path segment from one node to another. You position that rectangle along the node path and check for collisions with obstacles. If it collides, you can't go that way. Repeat for each path between nodes. You could also use a cylinder with a sufficient radius. If the paths can't be decomposed into straight segments, you could do something similar with a bounding box around the thing you are moving. Take that box and position it in steps along the candidate path. If it collides with anything along the way, it can't go that way. Note with either of these approaches I would suggest not trying to calculate the pathfinding every frame. You can do it piecemeal. Real things often start heading the wrong way and correct later anyhow so it might actually be more realistic. -Casey
Re: [pygame] Pathfinding
my game is 2d, but probably not tile-based. so your saying I can make it do only a few iterations per turn? how about doing the whole calculation beforehand, then not having to do many calculations? --- On Tue, 1/27/09, Casey Duncan ca...@pandora.com wrote: From: Casey Duncan ca...@pandora.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Tuesday, January 27, 2009, 5:06 PM On Jan 27, 2009, at 3:36 PM, Yanom Mobis wrote: is it easier to make the game tile-based? Probably, but it really depends on the details. if I make every pixel a node, and there are 2 obstacles really close together, how will I make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening? If this is a 3D game, what does a pixel mean? ;^) This could be done by vetting candidate routes using collision detection. Assuming you can reduce the path into a series of straight lines, you could create a rectangular prism with its height and depth set to the size of the bounding rectangle of the frontal area of the thing you are moving and it's length set to the distance of the path segment from one node to another. You position that rectangle along the node path and check for collisions with obstacles. If it collides, you can't go that way. Repeat for each path between nodes. You could also use a cylinder with a sufficient radius. If the paths can't be decomposed into straight segments, you could do something similar with a bounding box around the thing you are moving. Take that box and position it in steps along the candidate path. If it collides with anything along the way, it can't go that way. Note with either of these approaches I would suggest not trying to calculate the pathfinding every frame. You can do it piecemeal. Real things often start heading the wrong way and correct later anyhow so it might actually be more realistic. -Casey
Re: [pygame] Pathfinding
On Jan 27, 2009, at 4:48 PM, Yanom Mobis wrote: my game is 2d, but probably not tile-based. Ok, in that case a rectangle with a width equal to the frontal width of the thing parallel to the path will do. Or you could march a rectangle or circle down the candidate path to check for collisions. so your saying I can make it do only a few iterations per turn? It would scale much better that way, but may not be necessary if you are pathfinding for a small number of things. It all becomes vastly faster in 2D anyway 8) how about doing the whole calculation beforehand, then not having to do many calculations? Depends on whether there are few enough possible paths to do this in a small enough amount of time and memory. Tiling can help here because paths can be constrained by simple rules, still there can be too many possible start and end points to calculate ahead. -Casey
Re: [pygame] Pathfinding
Hey Yanom, Hmm... your game is probably not tile-based? sounds like you aren't very far along yet... I think you may be worrying a bit too much about pathfinding now. The truth of the matter is there is no single solution to pathfinding. There isn't even a best solution. There are some common tools for pathfinding that are well used, which it's nice to be aware of, but you're never gonna have something that works like: import pathfinding pathfinding.findpath(character, destination) All the little bits about how you represent your world, facts about what objects are in it, details about how you want your game characters to behave, design choices about their style of movement, how difficult you want the gameplay to be, all this stuff and more has a huge effect on how you'll want to do pathfinding. And you know what? _that's a good thing_ cause all those little facts are opportunities to cheat and hack and exploit things in smart ways. My real point is that right now, without knowing what you want to do with the game and the world, it's hard to figure out what you want to do with pathfinding. However, when you have a world and a character and all that, it's actually pretty darn easy. My advice to you is to *trust yourself* that when you've actually got a character that's moving, and getting stuck in some pit trying to get to his destination, that you'll be able to figure out a good solution to that. If you're worried about making bad choices now and walking into this horrible un-pathfindable case cause you didn't figure it out now, well don't worry. Most every problem has a good and fairly simple solution, if not, all code is refactorable, and for cases where it's too much work to refactor, then making mistakes is a great way to learn. So go program what you want until it's not working - you'll be able to fix it! and it will be a lot easier than things seem now. anyways, now back to chatting on the list about pathfinding... :) One fun solution to path-finding that has been good for me when there is no grid has been a visibility approach. Basically you do a collision check for the character going from where he is straight to the goal. If you find that he'll collide with something, then you turn till you've cleared the object, and do a collision check for moving past it - if the path is clear to move past it, then that becomes your next way point, and you do the original check towards your goal. If, however, you end up hitting something else trying to go past the first object, then you do the turn test on it, and so on till you get a waypoint. The trick to it is that when you find you'd hit something, there are 2 ways to turn, left and right. What this means is that for every object there are 2 choices, and each of those 2 choices may result in another object you'll have to pick between. What that means, is now you've got a search space to start exploring. You'll have to decide between trying left or trying right, and each choice leads to more choices. Boom, now you've got a place to use A*. On Tue, Jan 27, 2009 at 3:48 PM, Yanom Mobis ya...@rocketmail.com wrote: my game is 2d, but probably not tile-based. attachment: pathfinding_sloppy_sketch.png
Re: [pygame] Pathfinding
On Sun, Jan 25, 2009 at 07:16:38PM -0800, Yanom Mobis wrote: 1) How is pathfinding done? There are algorithms for it. Breadth-first search is the simplest one and works well for grids where the distance between nearby cells is the same. Dijkstra is a generalization that works for arbitrary maps. A* is essentially Dijkstra with an extra heuristic that makes it work faster, which is important for large maps. All of them find the shortest possible path. Wikipedia describes them all. 2) How do you prevent a moving sprite from being caught in a v-shaped rut made of obstacles? You use a pathfinding algorithm. On Sun, Jan 25, 2009 at 07:20:36PM -0800, Noah Kantrowitz wrote: 2) Alter the chain length score computation to reduce exploitation. Could you please translate that to something mere mortals without PhDs could understand? On Sun, Jan 25, 2009 at 09:13:28PM -0800, Bill Coderre wrote: There are still ways that this can get confused or beaten, of course. Until someone comes out with a low-cost traveling-salesman solver, however, whatever algorithm you find will have some snags. I don't see how traveling salesman applies here. Could you elaborate? My personal snag with A* is that the NPCs seem to know too much about the map and directly walk the most optimal path without exploration. Marius Gedminas -- niemeyer philiKON: I'm changing ZCML to parse files twice as fast.. philiKON niemeyer, weee benjiooh, I like it! philiKON how do you do that? niemeyer Lying philiKON i knew it * benji cries fowl! -- #zope3-dev signature.asc Description: Digital signature
Re: [pygame] Pathfinding
I used this AStar in some of my games, and it works very well: http://www.pygame.org/projects/9/195/ On Sun, 25 Jan 2009 19:16:38 -0800 (PST) Yanom Mobis ya...@rocketmail.com wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v-shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles? -- evil monkey there-is...@evil-monkey-in-my-closet.com
Re: [pygame] Pathfinding
Marius Gedminas wrote: My personal snag with A* is that the NPCs seem to know too much about the map and directly walk the most optimal path without exploration. One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. This could probably be implemented fairly cleverly by using generators. You'd probably have to experiment with different algorithms to find a more realistic approach - I suspect that A* would involve lots of wandering since it assumes constant access time for all known branches (whereas the character has to walk up and down the tree). DFS would probably be more realistic. --Mike
Re: [pygame] Pathfinding
This is the best A* Pathfinding tutorial, ever: http://theory.stanford.edu/~amitp/GameProgramming/http://theory.stanford.edu/%7Eamitp/GameProgramming/ -- Jake
Re: [pygame] Pathfinding
evil monkey wrote: I used this AStar in some of my games, and it works very well: http://www.pygame.org/projects/9/195/ I wrote an A* implementation awhile back for civil that might make another good example. Mine is a little different from the others I've seen as it can handle a few different map shapes including hex based maps. I've since packaged it separately and you can find it here: http://zhar.net/projects/gameai/ There are a few other python implementations of A* that I know of as well. They are also linked to from that page. A great site to read about path finding in general is Amit Patel's perennial site on the matter: http://www-cs-students.stanford.edu/~amitp/gameprog.html On Sun, 25 Jan 2009 19:16:38 -0800 (PST) Yanom Mobis ya...@rocketmail.com wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v-shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles? -- John Eikenberry [...@zhar.net - http://zhar.net] [PGP public key @ http://zhar.net/jae_at_zhar_net.gpg] __ Perfection is attained, not when no more can be added, but when no more can be removed. -- Antoine de Saint-Exupery signature.asc Description: Digital signature
Re: [pygame] Pathfinding
On Sun, Jan 25, 2009 at 7:16 PM, Yanom Mobis ya...@rocketmail.com wrote: 1) How is pathfinding done? So what are your pathfinding needs? what exactly is the character or game element that you need pathfinding for doing? or is this just research for you? On Mon, Jan 26, 2009 at 12:53 AM, Marius Gedminas mar...@gedmin.as wrote: My personal snag with A* is that the NPCs seem to know too much about the map and directly walk the most optimal path without exploration. I tend to agree with this - the whole purpose of A* is that when it's used, it finds a provably optimal path to it's goal, also because it is efficient, it has a strong tendency to find the same path every time.If those are desireable traits, then it is good for what you want to do. Very often though, what you actually want to achieve is an enemy or character that doesn't look stupid, can be somewhat unpredictable, and one that seems to have some personality (runs away from bad things, maybe changes it's speed when appropriate, or maybe it has a hard time turning). A* can help with the doesn't look stupid part, and if you play with the heuristic and the pathing costs right, you can get some personality, but it alone can't do everything, it's just one tool in making fun pathing. I personally think that the best thing with getting good pathing is really to get in there and play with things, and find tricks that work well for the domain of your game. It's good to get a good understanding of A*, and it's an awesome tool to be able to yield, but I always have it play a fairly small role in the final behavior of the pathing character or object, if it all. One things that I frequently find useful is doing a hierarchy of searches, at least in the case of large map games (like rts) - this is usually done by making checkpoints around the map (either by a designer, or by the ai as it plays) and having an estimate of cost between them. So like if you had a map of a bunch of islands connected by bridges (like a map of denmark or venice or something) you'd have a checkpoint stored for each island, and you'd have data storing which island is connected to which and the expected cost to travel using that bridge. Then you'd do the path finding on two levels - first complete pathfinding using the checkpoint and store that - then while the character is going from one checkpoint to the next, do pathfinding just between those 2 checkpoints - so if like an island is filled with stuff, the character would pathfind around that stuff on his way to the bridge. Another thing that can be helpful in getting fun is add a sense of memory to the character. This can complement hierarchical search very well, as having a memory of the whole map can be prohibitively expensive, and because it can give the player opportunities for strategic choices. Like in the bridge case above, maybe bridges can be out, or maybe the player can jam up an island somehow. In that case, then when the enemy is trying to follow the choices he made with the bridges and islands, and he is doing local pathfinding from one island to the next, he'll either fail to find a path in the maximum amount of looking he's allowed, or will find it costs much more than his checkpoint estimate told him. So at that point you update the checkpoint data, and then redo the checkpoint level planning. On Mon, Jan 26, 2009 at 9:01 AM, Michael George mdgeo...@cs.cornell.eduwrote: One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. in the language of A*, I guess you are suggesting ending the algorithm before it completes, then having the ai follow the stored path with the cheapest sum of (cost to follow the path to some point + heuristic estimate to finish from that point). That sounds like a good suggestion, it's often a practical choice choice because the cost to path grows greater than linear with the distance pathed, On Mon, Jan 26, 2009 at 9:01 AM, Michael George mdgeo...@cs.cornell.eduwrote: This could probably be implemented fairly cleverly by using generators. You'd probably have to experiment with different algorithms to find a more realistic approach - I suspect that A* would involve lots of wandering since it assumes constant access time for all known branches (whereas the character has to walk up and down the tree). DFS would probably be more realistic. I don't know exactly what you mean that A* would assume constant access time for all known branches - If you are taking about the idea that the character takes a lot of dead ends and walks back, you can work around that by varying the search depth when the character has taken too many dead ends. Also depth first search is not mutually exclusive to A* - In fact I find the best way to do A* is usually with Depth First Search with Iterative deepening, because it saves you the cost of having to store the outer hull of your breadth first
Re: [pygame] Pathfinding
Brian Fisher wrote: On Mon, Jan 26, 2009 at 9:01 AM, Michael George mdgeo...@cs.cornell.edu mailto:mdgeo...@cs.cornell.edu wrote: One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. in the language of A*, I guess you are suggesting ending the algorithm before it completes, then having the ai follow the stored path with the cheapest sum of (cost to follow the path to some point + heuristic estimate to finish from that point). That sounds like a good suggestion, it's often a practical choice choice because the cost to path grows greater than linear with the distance pathed, I was actually thinking that you make the A* function a generator. Each time it explores a new branch, it yields, and then the character moves to that branch. For DFS, iterative deepening this would work well, while for BFS, Dijkstra, or A* it would probably work poorly. --Mike
Re: [pygame] Pathfinding
John Eikenberry wrote: evil monkey wrote: I used this AStar in some of my games, and it works very well: http://www.pygame.org/projects/9/195/ ... http://zhar.net/projects/gameai/ There are a few other python implementations of A* that I know of as well. They are also linked to from that page. Productive has a slightly modified (IIRC faster) version of the A* at: http://arainyday.se/projects/python/AStar/ here: http://dev.laptop.org/git?p=projects/productive;a=tree;f=Productive.activity/astar;hb=HEAD we wound up using a hybrid system, where we'd try dead reckoning first, then try A* . Have fun, Mike -- Mike C. Fletcher Designer, VR Plumber, Coder http://www.vrplumber.com http://blog.vrplumber.com
Re: [pygame] Pathfinding
hi, the pygame.org page has a few pathfinding things here: http://pygame.org/tags/pathfinding Also, using the google search of the pygame website, you can find games that also use pathfinding in them. A lot of the classic algorithms are represented... Dijkstra's, A*, and breadth first. cheers, On Tue, Jan 27, 2009 at 9:15 AM, Mike C. Fletcher mcfle...@vrplumber.com wrote: John Eikenberry wrote: evil monkey wrote: I used this AStar in some of my games, and it works very well: http://www.pygame.org/projects/9/195/ ... http://zhar.net/projects/gameai/ There are a few other python implementations of A* that I know of as well. They are also linked to from that page. Productive has a slightly modified (IIRC faster) version of the A* at: http://arainyday.se/projects/python/AStar/ here: http://dev.laptop.org/git?p=projects/productive;a=tree;f=Productive.activity/astar;hb=HEAD we wound up using a hybrid system, where we'd try dead reckoning first, then try A* . Have fun, Mike -- Mike C. Fletcher Designer, VR Plumber, Coder http://www.vrplumber.com http://blog.vrplumber.com
Re: [pygame] Pathfinding
it seems to me that A* only works on tile-based games. What if my game isn't tile-based? --- On Sun, 1/25/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Sunday, January 25, 2009, 9:20 PM 1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles?
Re: [pygame] Pathfinding
I need to have an npc take a relatively short route from a to b. First priority isn't the shortest distance, it's getting there without getting stuck My game is in a futuristic setting, so taking the shortest path without exploring too much is reasonable because they would have GPS and the like. --- On Mon, 1/26/09, Brian Fisher br...@hamsterrepublic.com wrote: From: Brian Fisher br...@hamsterrepublic.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 11:55 AM On Sun, Jan 25, 2009 at 7:16 PM, Yanom Mobis ya...@rocketmail.com wrote: 1) How is pathfinding done? So what are your pathfinding needs? what exactly is the character or game element that you need pathfinding for doing? or is this just research for you? On Mon, Jan 26, 2009 at 12:53 AM, Marius Gedminas mar...@gedmin.as wrote: My personal snag with A* is that the NPCs seem to know too much about the map and directly walk the most optimal path without exploration.. I tend to agree with this - the whole purpose of A* is that when it's used, it finds a provably optimal path to it's goal, also because it is efficient, it has a strong tendency to find the same path every time.If those are desireable traits, then it is good for what you want to do. Very often though, what you actually want to achieve is an enemy or character that doesn't look stupid, can be somewhat unpredictable, and one that seems to have some personality (runs away from bad things, maybe changes it's speed when appropriate, or maybe it has a hard time turning). A* can help with the doesn't look stupid part, and if you play with the heuristic and the pathing costs right, you can get some personality, but it alone can't do everything, it's just one tool in making fun pathing. I personally think that the best thing with getting good pathing is really to get in there and play with things, and find tricks that work well for the domain of your game. It's good to get a good understanding of A*, and it's an awesome tool to be able to yield, but I always have it play a fairly small role in the final behavior of the pathing character or object, if it all. One things that I frequently find useful is doing a hierarchy of searches, at least in the case of large map games (like rts) - this is usually done by making checkpoints around the map (either by a designer, or by the ai as it plays) and having an estimate of cost between them. So like if you had a map of a bunch of islands connected by bridges (like a map of denmark or venice or something) you'd have a checkpoint stored for each island, and you'd have data storing which island is connected to which and the expected cost to travel using that bridge. Then you'd do the path finding on two levels - first complete pathfinding using the checkpoint and store that - then while the character is going from one checkpoint to the next, do pathfinding just between those 2 checkpoints - so if like an island is filled with stuff, the character would pathfind around that stuff on his way to the bridge. Another thing that can be helpful in getting fun is add a sense of memory to the character. This can complement hierarchical search very well, as having a memory of the whole map can be prohibitively expensive, and because it can give the player opportunities for strategic choices. Like in the bridge case above, maybe bridges can be out, or maybe the player can jam up an island somehow. In that case, then when the enemy is trying to follow the choices he made with the bridges and islands, and he is doing local pathfinding from one island to the next, he'll either fail to find a path in the maximum amount of looking he's allowed, or will find it costs much more than his checkpoint estimate told him. So at that point you update the checkpoint data, and then redo the checkpoint level planning. On Mon, Jan 26, 2009 at 9:01 AM, Michael George mdgeo...@cs.cornell.edu wrote: One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. in the language of A*, I guess you are suggesting ending the algorithm before it completes, then having the ai follow the stored path with the cheapest sum of (cost to follow the path to some point + heuristic estimate to finish from that point). That sounds like a good suggestion, it's often a practical choice choice because the cost to path grows greater than linear with the distance pathed, On Mon, Jan 26, 2009 at 9:01 AM, Michael George mdgeo...@cs.cornell.edu wrote: This could probably be implemented fairly cleverly by using generators. You'd probably have to experiment with different algorithms to find a more realistic approach - I suspect that A* would involve lots of wandering since it assumes constant access time for all known branches (whereas the character has to walk up and down the tree
Re: [pygame] Pathfinding
Yanom Mobis wrote: I need to have an npc take a relatively short route from a to b. First priority isn't the shortest distance, it's getting there without getting stuck My game is in a futuristic setting, so taking the shortest path without exploring too much is reasonable because they would have GPS and the like. Ah, then you have two options, as I see it. a) make the game a little more futuristic and give them bionic armour so they can just walk in a straight line and the obstacles bounce out of the way. (teleport machines would also work). b) read some of the messages and links and code that people have sent you and realise that A* is not inherently tile based, and that A* is not the only solution that has been explained. Douglas
Re: [pygame] Pathfinding
it seems to me that A* only works on tile-based games. What if my game isn't tile-based? A* works on 'nodes', where a node is just some location defined in the game space. Tile-based games have a very obvious node structure to them, and so A* is very easily adapted to them. But, really, there's not necessarily a lot of difference between applying A* to a tile-based game on the one hand and a network of location-nodes in a 3d space on the other.
RE: [pygame] Pathfinding
You need to construct a graph of possible paths. In a tile-based game this is easy, but it can be done in other kinds of games the same technique can be applied. A* is also used in other types of AIs, such a many board games. As for doing pathfinding in 3D worlds or similar, the word complex is a vast understatement. --Noah From: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 3:39 PM To: pygame-users@seul.org Subject: Re: [pygame] Pathfinding it seems to me that A* only works on tile-based games. What if my game isn't tile-based? --- On Sun, 1/25/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Sunday, January 25, 2009, 9:20 PM 1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles?
Re: [pygame] Pathfinding
On Sun, Jan 25, 2009 at 09:13:28PM -0800, Bill Coderre wrote: There are still ways that this can get confused or beaten, of course. Until someone comes out with a low-cost traveling-salesman solver, however, whatever algorithm you find will have some snags. On Jan 26, 2009, at 12:53 AM, Marius Gedminas wrote: I don't see how traveling salesman applies here. Could you elaborate? OK, so this was a semi-joke/handwave that if the walls are moving, one would probably need something that can solve routes in near-zero time because the routing would be changing a lot. If I were thinking harder, I would have remembered that the Traveling Salesman Problem is concerned with visiting ALL nodes on a network, and not just finding a single (hopefully quick) route from A to B, and therefore it's not applicable to this problem at all.
Re: [pygame] Pathfinding
Yanom Mobis wrote: it seems to me that A* only works on tile-based games. What if my game isn't tile-based? I'm not sure you think that. A* (or any other pathfinding algorithm) will work for any search tree. You do need some sort of heuristic, though, that estimates how far any given position is from the goal. That's usually pretty easy though if position really corresponds in some way to a position in space -- just use the Euclidian distance to the goal as your heuristic. Best, - Joe
Re: [pygame] Pathfinding
Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v-shaped rut made of obstacles? Like this: __ A - # | B __| Others have already talked about the A* Algorithm (http://en.wikipedia.org/wiki/A*). Here's my implementation of it: http://kschnee.xepher.net/code/080721a_star_pathfinding.zip Screenshots: http://kschnee.xepher.net/pics/080720a_star.jpg http://kschnee.xepher.net/pics/080721a_star.jpg In English, you have the AI look at a map of costs to enter each area, and compute a minimum-cost path. A* automatically handles escaping from ruts, by terminating the paths it's considering when they prove too expensive. (You can treat walls as having an infinite entry cost.) One interesting feature of A* is that it assumes the AI has perfect knowledge, something fine for games but flawed for real AI. XKCD's comment on this sort of cost-computation method: http://imgs.xkcd.com/comics/genetic_algorithms.png
RE: [pygame] Pathfinding
a graph, as in just a regular x, y kind of thing? I don't need an overly complex library, is something less complex available? --- On Mon, 1/26/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: RE: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 6:13 PM You need to construct a graph of possible paths. In a tile-based game this is easy, but it can be done in other kinds of games the same technique can be applied. A* is also used in other types of AIs, such a many board games. As for doing pathfinding in 3D worlds or similar, the word “complex” is a vast understatement. --Noah From: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 3:39 PM To: pygame-users@seul.org Subject: Re: [pygame] Pathfinding it seems to me that A* only works on tile-based games. What if my game isn't tile-based? --- On Sun, 1/25/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Sunday, January 25, 2009, 9:20 PM 1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles?
Re: [pygame] Pathfinding
Complex distance evaluation isn't necessary, but the sprite never getting stuck is. --- On Mon, 1/26/09, Joe Strout j...@strout.net wrote: From: Joe Strout j...@strout.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 6:11 PM Yanom Mobis wrote: it seems to me that A* only works on tile-based games. What if my game isn't tile-based? I'm not sure you think that. A* (or any other pathfinding algorithm) will work for any search tree. You do need some sort of heuristic, though, that estimates how far any given position is from the goal. That's usually pretty easy though if position really corresponds in some way to a position in space -- just use the Euclidian distance to the goal as your heuristic. Best, - Joe
Re: [pygame] Pathfinding
My game isn't tile-based (probably, I haven't made it yet), but it is 2-d --- On Mon, 1/26/09, NBarnes nbar...@gmail.com wrote: From: NBarnes nbar...@gmail.com Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 6:10 PM it seems to me that A* only works on tile-based games. What if my game isn't tile-based? A* works on 'nodes', where a node is just some location defined in the game space. Tile-based games have a very obvious node structure to them, and so A* is very easily adapted to them. But, really, there's not necessarily a lot of difference between applying A* to a tile-based game on the one hand and a network of location-nodes in a 3d space on the other.
Re: [pygame] Pathfinding
A graph, as in one from graph theory: http://en.wikipedia.org/wiki/Graph_theory On Tue, Jan 27, 2009 at 12:12 PM, Yanom Mobis ya...@rocketmail.com wrote: Complex distance evaluation isn't necessary, but the sprite never getting stuck is. --- On Mon, 1/26/09, Joe Strout j...@strout.net wrote: From: Joe Strout j...@strout.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 6:11 PM Yanom Mobis wrote: it seems to me that A* only works on tile-based games. What if my game isn't tile-based? I'm not sure you think that. A* (or any other pathfinding algorithm) will work for any search tree. You do need some sort of heuristic, though, that estimates how far any given position is from the goal. That's usually pretty easy though if position really corresponds in some way to a position in space -- just use the Euclidian distance to the goal as your heuristic. Best, - Joe
RE: [pygame] Pathfinding
http://en.wikipedia.org/wiki/Graph_(mathematics) http://en.wikipedia.org/wiki/Graph_(mathematics) If you are unclear on what a graph is, I wouldn't recommend trying to write a pathfinding system youself. Perhaps try something higher-level or a library that includes one. --Noah From: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 5:12 PM To: pygame-users@seul.org Subject: RE: [pygame] Pathfinding a graph, as in just a regular x, y kind of thing? I don't need an overly complex library, is something less complex available? --- On Mon, 1/26/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: RE: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 6:13 PM You need to construct a graph of possible paths. In a tile-based game this is easy, but it can be done in other kinds of games the same technique can be applied. A* is also used in other types of AIs, such a many board games. As for doing pathfinding in 3D worlds or similar, the word complex is a vast understatement. --Noah From: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 3:39 PM To: pygame-users@seul.org Subject: Re: [pygame] Pathfinding it seems to me that A* only works on tile-based games. What if my game isn't tile-based? --- On Sun, 1/25/09, Noah Kantrowitz n...@coderanger.net wrote: From: Noah Kantrowitz n...@coderanger.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Sunday, January 25, 2009, 9:20 PM 1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles?
Re: [pygame] Pathfinding
Yanom Mobis wrote: Complex distance evaluation isn't necessary, but the sprite never getting stuck is. The sprite will never get stuck with any of the algorithms we have discussed. And you're right, you don't need a complex distance evaluation for A* -- a simple one will do. (Though the better your heuristic is, the more efficiently A* will work.) Best, - Joe
Re: [pygame] Pathfinding
so is A* the easiest to use? --- On Mon, 1/26/09, Joe Strout j...@strout.net wrote: From: Joe Strout j...@strout.net Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org Date: Monday, January 26, 2009, 8:14 PM Yanom Mobis wrote: Complex distance evaluation isn't necessary, but the sprite never getting stuck is. The sprite will never get stuck with any of the algorithms we have discussed. And you're right, you don't need a complex distance evaluation for A* -- a simple one will do. (Though the better your heuristic is, the more efficiently A* will work.) Best, - Joe
Re: [pygame] Pathfinding
Yanom Mobis wrote: so is A* the easiest to use? They're all about the same; they differ only in what order new nodes are examined. If you have a cost function (which you do), you can do a least-cost search. If you also have a heuristic (which I think you do), you can do A*. They'll both produce the same answer but A* will generally produce it a little faster. Best, - Joe
Re: [pygame] Pathfinding
Have you played any of the unreal tournament games? The way it pathfinds is like what you're asking. It uses a graph ( a bunch of nodes connecting to each other. It actually pre-calculates pathfinding, but you don't need to worry about that at first ) The link posted has a good image: http://en.wikipedia.org/wiki/Graph_%28mathematics%29 ( look at the first one ) Looking at the image, image 1 = health,l 2=flak gun, 3 = ammo, 5 = flag, etc... If a bot wants to go from 3 to 5, you can use A* to find the path. It just needs a graph ( a bunch of nodes, which can connect to other nodes ) The actual (x,y,z) location of the nodes doesn't matter. ( But if the distance is too far, you need to take that into account by the weight, or, add a node between them ) On Mon, Jan 26, 2009 at 7:11 PM, Yanom Mobis ya...@rocketmail.com wrote: a graph, as in just a regular x, y kind of thing? I don't need an overly complex library, is something less complex available? You can use a regular list-type of tiles. And each list item holds a list of pointers to all tiles that it connects to. If you are doing a tile based map, using a 2D array could simplify things. ( using numPy ) # this is a bad example, but, to give you an idea: class Tile(): def __init__(self): self.clist = [] t1 = Tile() t2 = Tile() t3 = Tile() # 1 connects to 2 and 3 t1.clist.append( t2 ) t1.clist.append( t3 ) # 2 connects to 1 t2.clist.append( t1 ) # 3 connects to 1 t3.clist.append( t1 ) # map a list of Tile()s map = [t1, t2, t3] -- Jake
Re: [pygame] Pathfinding
1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles?
Re: [pygame] Pathfinding
On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: 1) How is pathfinding done? 2) How do you prevent a moving sprite from being caught in a v- shaped rut made of obstacles? Like this: __ A - # | B __| Where A and B are the points the sprite needs to travel, # is the sprite, - is the direction the sprite is moving, and _ and | are obstacles? Naive algorithms often head directly toward a goal, and then get stuck when, in order to achieve the goal, they have to move away from it. Do some reading on local maximum problem and hill-climbing algorithm. The way to get out of this rut (heh heh) is to use a better algorithm. For example, if you have a known map where the obstacles don't move, you can make a pre-computed route that your guy # walks along. That's an extremely popular way to do it, and it does really well for dungeon- y type video games. Guard on patrol. The super deee-luxe, full-fat algorithm for when the obstacles/goals are moving is to use an algorithm that plots a complete route to the goal, every time, and move along the path. There are still ways that this can get confused or beaten, of course. Until someone comes out with a low-cost traveling-salesman solver, however, whatever algorithm you find will have some snags.
