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] pygame.midi using portmidi?
Hi, this notes a patch for 10.5sdk http://lists.create.ucsb.edu/pipermail/media_api/2009-January/000703.html Also found a section on OSX here: http://cratel.wichita.edu/cratel/cratel_pyportmidi Also, have you tried the .c test programs that come with portmidi? cheers, On Sun, Jan 25, 2009 at 9:15 PM, Brian Fisher br...@hamsterrepublic.com wrote: So I got pygame building on mac with portmidi now - although I can't seem to get the midi.py example to do anything. the xcode proj for portmidi seems to have the porttime sources incorporated into it, rather than built as a separate lib, so the porttime dependency doesn't exist, which was causing trouble. Also the static libportmidi.a lib requires linkage to the CoreMidi framework, which was also causing trouble. So I decided to kill 2 birds with one stoney-hack and made PORTTIME dependency be a dependency on porttime. But now when I install the pygame on a machine with a midi keyboard attached, and run examples/midi.py with either --output or --list, it waits a long time, then prints in stat: : No such file or directory 4 times. looking at portmidi's sources, that error seems to com from it trying to read the /PortMidi/PM_RECOMMENDED_INPUT_DEVICE setting from some prefs file com.apple.java.util.prefs.plist as part of it's initialization. It seems really bizarre and rather dumb to me that portmidi would use java for anything, and I'm starting to wonder if the thing even works on Leopard... On Tue, Jan 13, 2009 at 2:49 PM, René Dudfield ren...@gmail.com wrote: I think with portmidi, compiling it ourselves on mac is the way to go. Seemed easy to compile on win/linux... so hopefully it compiles ok on mac too.
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
[pygame] Python 2.5.4
is it possible to install python2.5.4 on top of 2.5.2 ( ./configure make sudo make install ) on Linux? Will this break any packages?
Re: [pygame] Python 2.5.4
yes it will break packages On Tue, Jan 27, 2009 at 2:23 PM, Yanom Mobis ya...@rocketmail.com wrote: is it possible to install python2.5.4 on top of 2.5.2 ( ./configure make sudo make install ) on Linux? Will this break any packages?
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] Python 2.5.4
Minor Python versions are simply bug fixes. Python 2.5.4 libraries are intended as drop-in replacements for those of 2.5.2. Extension modules compiled and linked against 2.5.2 will also work with 2.5.4. So unless Linux version control is so finicky as to operate on the minor version level it should be possible to uninstall 2.5.2 and install 2.5.4 in its place. Lenard. René Dudfield wrote: yes it will break packages On Tue, Jan 27, 2009 at 2:23 PM, Yanom Mobis ya...@rocketmail.com wrote: is it possible to install python2.5.4 on top of 2.5.2 ( ./configure make sudo make install ) on Linux? Will this break any packages?
