You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

S  M  T  W  T  F  S 




1
(1) 
2
(9) 
3
(1) 
4
(6) 
5
(13) 
6
(21) 
7
(17) 
8
(21) 
9
(7) 
10
(5) 
11
(6) 
12

13

14
(4) 
15
(22) 
16
(9) 
17
(13) 
18
(4) 
19

20
(9) 
21
(16) 
22
(5) 
23
(9) 
24

25
(1) 
26

27

28
(19) 
29
(2) 
30



From: toms @ cyanide <tmachado@cy...>  20061129 17:50:11

Hi all! I'm looking for any kind of documentation about how to implement AI for a team sports game like soccer (for example). For now, I know about the command hierarchy method, and some others read in the 3 AI gems, but I am also open for any other resources (web, mailing list, papers...) Cheers 
From: Thatcher Ulrich <tu@tu...>  20061129 10:00:59

I wish I could find it online, but FYI Sean Barrett did a pretty thorough gridpathfinding series, with code, in Game Developer mag. Here are some tantalizing links, maybe you can chase down the actual content: http://www.gdmag.com/archive/apr05.htm http://www.gdmag.com/archive/junjul05.htm http://www.gdmag.com/code.htm T On 11/28/06, Alias=99 <aliasrob@...> wrote: > Hi guys, > > I'm currently working on some 2d grid based pathfinding stuff, and I'm a > little unsatisfied with the performance of A*. It seems to take a very br= ute > force approach to the problem, and is constantly causing CPU issues. > > Are there any more elegant/modern algorithms which have been developed wh= ich > might fit my purposes? I'm just looking to find a simple path between to > points, avoiding obstacles. Grid squares are either empty or solid. > > Any pointers would be much appreciated, > > Cheers, > Alias > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share y= our > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > 
From: Jon Watte <hplus@mi...>  20061128 23:00:27

Tony Cox wrote: > You do this by forming the Delaunay triangulation of the vertices demarking the border of each region. > > Ah, the crucial missing step. My solution (using Voronoi) was along the terms of creating nodes as centerpoints of passable regions. I understand now  your model is good! Cheers, / h+ 
From: Tony Cox <tonycox@mi...>  20061128 22:45:28

Ah, you misunderstand. The vertices you are doing the Delaunay triangulation are not the nodes of = the graph to traverse. The point is to coalesce cells into homogenous regio= ns and then dissect those regions into triangles. You do this by forming th= e Delaunay triangulation of the vertices demarking the border of each regio= n. Then you can take the graph formed by the connecting the center of each tri= angle to the centers of its three neighbors. You run A* on this graph. The point is to make the resulting path easier to deal with by starting wit= h a triangulation instead of arbitrarily shaped regions. In particular, the= line segment joining the centers of two adjacent regions never intersects = any other region  not true with an arbitrary carving up into say, rectangl= es. This allows a na=EFve pathfollower to just walk to the center of whate= ver triangle it's in, follow the path, and then walk from the center of the= destination triangle to the first target point. As you say, being 3connected doesn't really matter for A*, I just mentione= d it as a possibly handy sideeffect of this approach since you can make yo= ur data structure have a fixed number of neighbors for each node rather tha= n an arbitrary list. Tony Cox  Director of Engineering Microsoft Game Studios Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithms= listbounces@...] On Behalf Of Jon Watte Sent: Tuesday, November 28, 2006 1:57 PM To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms than= A*? Tony Cox wrote: > > The graph of the regions is just an abstract data structure. In the > case of a Delaunay triangulation, you know that each region only has > (at most) 3 neighbors, which makes the data structure fairly simple > (just have three pointers or indices to adjacent nodes). > http://en.wikipedia.org/wiki/Delaunay_triangulation > > > The vertices are the actual nodes, so any outgoing edge from a vertex is a neighbor. The number of neighbors can be any  you really want the dual of the Delaunay which is the Voronoi diagram. That being said, an A* for an Nconnected graph is not really any harder than an A* for a 3connected graph. Cheers, 
From: Jon Watte <hplus@mi...>  20061128 21:57:02

Tony Cox wrote: > > The graph of the regions is just an abstract data structure. In the > case of a Delaunay triangulation, you know that each region only has > (at most) 3 neighbors, which makes the data structure fairly simple > (just have three pointers or indices to adjacent nodes). > http://en.wikipedia.org/wiki/Delaunay_triangulation > > > The vertices are the actual nodes, so any outgoing edge from a vertex is a neighbor. The number of neighbors can be any  you really want the dual of the Delaunay which is the Voronoi diagram. That being said, an A* for an Nconnected graph is not really any harder than an A* for a 3connected graph. Cheers, / h+ 
From: <christer_ericson@pl...>  20061128 19:39:16

David P wrote: > For the optimal A* performance you need to take care of the heuristic > you use. Wrong heuristic can cause the algorithm to search the whole grid. > Check http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S7 > for different heuristics and implications. While it's likely there are other reasons Rob is seeing performance issues, David's is actually a _very_ important point. My pet peeve with people using A* for pathfinding is that they are, for unknown reasons, obsessed with producing the _shortest_ path. The problem with this is that switching from an admissible (underestimating) heuristic to an nonadmissible (overestimating) heuristic can _drastically_ reduce the search effort, at the cost of returning paths that are no longer guaranteed to be the shortest. I strongly suggest that people who do A* pathfinding try nonadmissible heuristics. Christer Ericson http://realtimecollisiondetection.net/ 
From: <aliasrob@gm...>  20061128 18:51:12

> > > > > The implementation of A* I'm using is designed for simple grids and I > was hoping not to have to rework it. > > You're asking for a better solution, but you don't want to rework your > A*? That sounds a little bit like conflicting goals, to me :) > To clarify  I'm open to reworking the algorithm, but I'm also open to throwing it out and starting from scratch. I was hoping to tweak it, rather than rewrite it, but I'll do whatever needs doing! Thanks for all your input! Alias 
From: Jon Watte <hplus@mi...>  20061128 18:39:00

A* is pretty much as good as it gets for general algorithms. If you can preprocess, there are better algorithms, such as finding large, fully connected areas, and merging them into convex slabs (which may have more than one entry/exit per side), and running A* on a graph of slabs instead of a graph of grid cells. The easiest kind of slab to generate is a simple rectangle. Once you find an empty cell, expand greedily along both axes until it runs into an obstacle, then expand along one of the axes until it runs into an obstacle  that's your slab. Repeat for entire grid. You can assume that the connectivity is from center of each slab opening to other center, and then straighten up the path once it's found. Other preprocessing includes finding the outline of all obstacles as polygons, and marking vertices on this outline, and calculating LOS visibility between these vertices to generate a connectivity graph. Then run A* on that. This will tend to "round corners" and sometimes even "hug walls," but that might be what you want. Especially if some sides are more dangerous than others, and thus can be given a higher cost (like, facing the enemy :). I just saw some replies to your questions, btw: > The implementation of A* I'm using is designed for simple grids and I was hoping not to have to rework it. You're asking for a better solution, but you don't want to rework your A*? That sounds a little bit like conflicting goals, to me :) Cheers, / h+ Alias™ wrote: > Hi guys, > > I'm currently working on some 2d grid based pathfinding stuff, and I'm > a little unsatisfied with the performance of A*. It seems to take a > very brute force approach to the problem, and is constantly causing > CPU issues. > > Are there any more elegant/modern algorithms which have been developed > which might fit my purposes? I'm just looking to find a simple path > between to points, avoiding obstacles. Grid squares are either empty > or solid. > > Any pointers would be much appreciated, > > Cheers, > Alias >  > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV >  > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Tony Cox <tonycox@mi...>  20061128 18:04:37

It depends how much postprocessing you want to do on the path. You'll have= to do at least some (otherwise you get very robotic looking motion), so ho= w you cope with the problem really depends on the lowlevel path following = behavior of the units. Just using the center of each region can work if you have the right constra= ints  in particular, you want to make sure that the line segment joining t= he centers of two adjacent regions doesn't intersect any other region. If y= ou use a triangulation as your tessellation (instead of rectangular regions= as you have below) then you can guarantee that property, which is quite us= eful. You also want to make the regions as compact as possible (avoid long = skinny regions) to get the best looking paths  you'll have to postprocess= anyway to get a good looking result, but starting from a good initial path= goes a long way. The approach I have used in the past is to form the Delau= nay triangulation, but other approaches could work too. The graph of the regions is just an abstract data structure. In the case of= a Delaunay triangulation, you know that each region only has (at most) 3 n= eighbors, which makes the data structure fairly simple (just have three poi= nters or indices to adjacent nodes). http://en.wikipedia.org/wiki/Delaunay_= triangulation Tony Cox  Director of Engineering Microsoft Game Studios From: gdalgorithmslistbounces@... [mailto:gdalgorithms= listbounces@...] On Behalf Of Alias(tm) Sent: Monday, November 27, 2006 7:11 PM To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms than= A*? Hi Tony, I have considered this approach  however, I'm not entirely sure how I'd tr= ace the path from larger clusters to the smaller, more complex areas     B   A    C   Say node A is a larger cluster of 4 identical cells. When I'm traversing th= at square, do I just assume that the path would go through the centre, and = list each adjacent cell in an array or something? Currently the algorithm j= ust uses a set of x y coordinates to address each node, so when expanding a= cell it looks to n1 and n+1 to find neighbour cells. I could change this = though. Am I along the right lines with this? Cheers, 
From: Daniel Yeung <dyeung@li...>  20061128 15:33:32

I think you should really look closer at your use of the open and close lists. Are you using a Binary Heap for holding storing these collections? I implemented one previously, with quick membership tests and removals, and the speed gains were huge. Also, as your only requirement is that a cell in the grid is either vacant or occupied, have you upped the cost of the occupied cells so they never get considered as potential path candidates? =20 =20 _____ =20 From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Alias(tm) Sent: 28 November 2006 12:14 To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithmsthanA*? =20 Hi Daniel I'm thinking that the grid size is the main problem. I'm working with the Flash 8 AS2 AVM so performance is pretty crappy at the best of times  I'm going to look at optimising the heuristic, and possibly clustering cells together so that I can reduce the workload on sparser parts of the geometry. I haven't really been able to profile the scalability of the lists, although the performance seems to rapidly swing from "good" to "almost crashing", (I may be dealing with an actual bug rather than an inefficient algorithm in that particular case).=20 As far as memory access goes, the AVM uses reference counted garbage collection, with only marginal control over memory usage  I'd be interested in what kind of changes you used to optimise your PS2 implementation though. I might be able to do something similar (although there's a lot less lowlevel control, as you can probably imagine).=20 Threading  yes, I've done that already. That definitely helps, but I need a more responsive solution. Thanks for your help, Alias On 28/11/06, Daniel Yeung <dyeung@...> wrote: Based on the size of your grids, I would say your implementation of the A* algorithm is the main problem here. Without looking through your source, my 1st suggestion would be to examine the containers used for your open and closed lists.=20 What is the "BigO" for insertions, removals and lookups? Secondly, what platform are you working on? We implemented tilebased memory access for a game on PS2 to increase cache efficiency, because of the way memory tends to be accessed in the A* algorithm. Thirdly, have you thought about splitting up the processing of the algorithm so that it does at most "n" traversals per game tick, and continues if the path is still incomplete? Or running on another thread? =20 _____ =20 From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Alias(tm) Sent: 28 November 2006 03:05 To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms thanA*? =20 Hi Christer, Sure! OK:  Grid varies between 100x100 to I'd say 500x500 max.  Map is completely static  CPU issues are that the algorithm is locking up when looking through longer paths  My implementation might not be that efficient, and I am currently reworking it for efficiency, however I'm wondering if A* is the right approach for this particular problem.=20 Basically, the issue is that my grid may be way too large for a straightforward A* implementation, so I think I need to look at alternatives. Cheers, Alias On 28/11/06, christer_ericson@... <christer_ericson@... > wrote: > I'm currently working on some 2d grid based pathfinding stuff, and=20 > I'm a little unsatisfied with the performance of A*. It seems to > take a very brute force approach to the problem, and is constantly > causing CPU issues. > > Are there any more elegant/modern algorithms which have been=20 > developed which might fit my purposes? I'm just looking to find a > simple path between to points, avoiding obstacles. Grid squares are > either empty or solid. You need to provide more information to get a good answer. For example, how big is your grid? Do grid cells change status dynamically or is the map static? What is the cell connectivity? What are your "CPU issues" and did you implement your A* algorithm in an efficient way? Etc.=20 For a small static map you can precompute a twodimensional table that for entry (A,B), where A represents the start cell and B the end cell, contains two bits that specify whether to go N, S, E, or W from the=20 current start cell to end up at a new "start" cell. This solution is obviously O(1) in terms of speed for finding the next position to go to, which is hard to beat. The only problem is that, while a 20x20 grid takes ~20K of precomputed=20 data, a 100x100 grid requires ~12MB of precomputed data (if I didn't get those numbers exactly right, at least you get the idea). With more detail, people are more likely to be able to provide an answer that might be more helpful to you.=20 Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica   Take Surveys. Earn Cash. Influence the Future of IT=20 Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V=20 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =20   Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash=20 http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V=20 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@...=20 https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =20 
From: <aliasrob@gm...>  20061128 12:13:59

Hi Daniel I'm thinking that the grid size is the main problem. I'm working with the Flash 8 AS2 AVM so performance is pretty crappy at the best of times  I'm going to look at optimising the heuristic, and possibly clustering cells together so that I can reduce the workload on sparser part= s of the geometry. I haven't really been able to profile the scalability of the lists, although the performance seems to rapidly swing from "good" to "almost crashing", (I may be dealing with an actual bug rather than an inefficient algorithm in that particular case). As far as memory access goes, the AVM uses reference counted garbage collection, with only marginal control over memory usage  I'd be intereste= d in what kind of changes you used to optimise your PS2 implementation though= . I might be able to do something similar (although there's a lot less lowlevel control, as you can probably imagine). Threading  yes, I've done that already. That definitely helps, but I need = a more responsive solution. Thanks for your help, Alias On 28/11/06, Daniel Yeung <dyeung@...> wrote: > > Based on the size of your grids, I would say your implementation of the > A* algorithm is the main problem here. Without looking through your sourc= e, > my 1st suggestion would be to examine the containers used for your open > and closed lists. > > What is the "BigO" for insertions, removals and lookups? > > Secondly, what platform are you working on? We implemented tilebased > memory access for a game on PS2 to increase cache efficiency, because of = the > way memory tends to be accessed in the A* algorithm. > > Thirdly, have you thought about splitting up the processing of the > algorithm so that it does at most "n" traversals per game tick, and > continues if the path is still incomplete? Or running on another thread? > > >  > > *From:* gdalgorithmslistbounces@... [mailto: > gdalgorithmslistbounces@...] *On Behalf Of *Alias=99 > *Sent:* 28 November 2006 03:05 > *To:* Game Development Algorithms > *Subject:* Re: [Algorithms] Pathfinding in a 2d grid  better algorithms > thanA*? > > > > Hi Christer, > > Sure! > > OK: > >  Grid varies between 100x100 to I'd say 500x500 max. >  Map is completely static >  CPU issues are that the algorithm is locking up when looking through > longer paths >  My implementation might not be that efficient, and I am currently > reworking it for efficiency, however I'm wondering if A* is the right > approach for this particular problem. > > Basically, the issue is that my grid may be way too large for a > straightforward A* implementation, so I think I need to look at > alternatives. > > Cheers, > Alias > > On 28/11/06, *christer_ericson@...* <christer_ericson@...= aystation.sony.com > > wrote: > > > I'm currently working on some 2d grid based pathfinding stuff, and > > I'm a little unsatisfied with the performance of A*. It seems to > > take a very brute force approach to the problem, and is constantly > > causing CPU issues. > > > > Are there any more elegant/modern algorithms which have been > > developed which might fit my purposes? I'm just looking to find a > > simple path between to points, avoiding obstacles. Grid squares are > > either empty or solid. > > You need to provide more information to get a good answer. For example, > how big is your grid? Do grid cells change status dynamically or is the > map static? What is the cell connectivity? What are your "CPU issues" > and did you implement your A* algorithm in an efficient way? Etc. > > For a small static map you can precompute a twodimensional table that > for entry (A,B), where A represents the start cell and B the end cell, > contains two bits that specify whether to go N, S, E, or W from the > current start cell to end up at a new "start" cell. This solution is > obviously O(1) in terms of speed for finding the next position to go to, > which is hard to beat. > > The only problem is that, while a 20x20 grid takes ~20K of precomputed > data, a 100x100 grid requires ~12MB of precomputed data (if I didn't > get those numbers exactly right, at least you get the idea). > > With more detail, people are more likely to be able to provide an > answer that might be more helpful to you. > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > 
From: Daniel Yeung <dyeung@li...>  20061128 11:56:44

Based on the size of your grids, I would say your implementation of the A* algorithm is the main problem here. Without looking through your source, my 1st suggestion would be to examine the containers used for your open and closed lists.=20 What is the "BigO" for insertions, removals and lookups? Secondly, what platform are you working on? We implemented tilebased memory access for a game on PS2 to increase cache efficiency, because of the way memory tends to be accessed in the A* algorithm. Thirdly, have you thought about splitting up the processing of the algorithm so that it does at most "n" traversals per game tick, and continues if the path is still incomplete? Or running on another thread? =20 _____ =20 From: gdalgorithmslistbounces@... [mailto:gdalgorithmslistbounces@...] On Behalf Of Alias(tm) Sent: 28 November 2006 03:05 To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms thanA*? =20 Hi Christer, Sure! OK:  Grid varies between 100x100 to I'd say 500x500 max.  Map is completely static  CPU issues are that the algorithm is locking up when looking through longer paths  My implementation might not be that efficient, and I am currently reworking it for efficiency, however I'm wondering if A* is the right approach for this particular problem.=20 Basically, the issue is that my grid may be way too large for a straightforward A* implementation, so I think I need to look at alternatives. Cheers, Alias On 28/11/06, christer_ericson@... <christer_ericson@... > wrote: > I'm currently working on some 2d grid based pathfinding stuff, and=20 > I'm a little unsatisfied with the performance of A*. It seems to > take a very brute force approach to the problem, and is constantly > causing CPU issues. > > Are there any more elegant/modern algorithms which have been=20 > developed which might fit my purposes? I'm just looking to find a > simple path between to points, avoiding obstacles. Grid squares are > either empty or solid. You need to provide more information to get a good answer. For example, how big is your grid? Do grid cells change status dynamically or is the map static? What is the cell connectivity? What are your "CPU issues" and did you implement your A* algorithm in an efficient way? Etc.=20 For a small static map you can precompute a twodimensional table that for entry (A,B), where A represents the start cell and B the end cell, contains two bits that specify whether to go N, S, E, or W from the=20 current start cell to end up at a new "start" cell. This solution is obviously O(1) in terms of speed for finding the next position to go to, which is hard to beat. The only problem is that, while a 20x20 grid takes ~20K of precomputed=20 data, a 100x100 grid requires ~12MB of precomputed data (if I didn't get those numbers exactly right, at least you get the idea). With more detail, people are more likely to be able to provide an answer that might be more helpful to you.=20 Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica   Take Surveys. Earn Cash. Influence the Future of IT=20 Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys  and earn cash http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDE V _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 =20 
From: david pangerl <david@zo...>  20061128 08:02:53

Hi Alias, For the optimal A* performance you need to take care of the heuristic you use. Wrong heuristic can cause the algorithm to search the whole grid. Check http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S7 for different heuristics and implications. Cheers, DAVID  http://www.zootfly.com Alias^(TM) wrote: > Hi Christer, > > Sure! > > OK: > >  Grid varies between 100x100 to I'd say 500x500 max. >  Map is completely static >  CPU issues are that the algorithm is locking up when looking through > longer paths >  My implementation might not be that efficient, and I am currently > reworking it for efficiency, however I'm wondering if A* is the right > approach for this particular problem. > > Basically, the issue is that my grid may be way too large for a > straightforward A* implementation, so I think I need to look at > alternatives. > > Cheers, > Alias > > On 28/11/06, *christer_ericson@... > <mailto:christer_ericson@...>* > <christer_ericson@... > <mailto:christer_ericson@...>> wrote: > > > I'm currently working on some 2d grid based pathfinding stuff, and > > I'm a little unsatisfied with the performance of A*. It seems to > > take a very brute force approach to the problem, and is constantly > > causing CPU issues. > > > > Are there any more elegant/modern algorithms which have been > > developed which might fit my purposes? I'm just looking to find a > > simple path between to points, avoiding obstacles. Grid squares are > > either empty or solid. > > You need to provide more information to get a good answer. For > example, > how big is your grid? Do grid cells change status dynamically or > is the > map static? What is the cell connectivity? What are your "CPU > issues" > and did you implement your A* algorithm in an efficient way? Etc. > > For a small static map you can precompute a twodimensional table that > for entry (A,B), where A represents the start cell and B the end cell, > contains two bits that specify whether to go N, S, E, or W from the > current start cell to end up at a new "start" cell. This solution is > obviously O(1) in terms of speed for finding the next position to > go to, > which is hard to beat. > > The only problem is that, while a 20x20 grid takes ~20K of > precomputed > data, a 100x100 grid requires ~12MB of precomputed data (if I didn't > get those numbers exactly right, at least you get the idea). > > With more detail, people are more likely to be able to provide an > answer that might be more helpful to you. > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to > share your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > <http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV>; > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > <mailto:GDAlgorithmslist@...> > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > >Take Surveys. Earn Cash. Influence the Future of IT >Join SourceForge.net's Techsay panel and you'll get the chance to share your >opinions on IT & business topics through brief surveys  and earn cash >http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > > > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > >Internal Virus Database is outofdate. >Checked by AVG Free Edition. >Version: 7.1.392 / Virus Database: 268.11.4/424  Release Date: 21.8.2006 > > 
From: <cedksatria@gm...>  20061128 05:51:54

I was talking about dividing you path into zones. Zones are connected together. then you build you first high level path usin= g zones as nodes for the A*. Then for each zone you can compute finer path. n my previous project we were using this with the ability to cnnect zones dynamically (like opening a door for example). What's nice with this is tha= t the first step of the algorithm can get rid of a very big part of the grid, so accelerating the second part :) Cedric =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D On 11/28/06, Alias=99 <aliasrob@... > wrote: > > Hi Cedric, > > The grid size will vary, but it is currently around 100x100, and could > easily get much larger. > > Are you talking about precomputing some kind of hierachical tree, like a > quadtree or something? I have considered that, but the implementation of = A* > I'm using is designed for simple grids and I was hoping not to have to > rework it. Sounds like an interesting approach though. > > Cheers, > Alias > > On 28/11/06, C=E9dric CAILLAUD < cedksatria@...> wrote: > > > > Hi, > > > > What is the size of your grid ? > > I worked on a project where we had some issues with pathfinding > > performances on large grids. Then AI guys implemented a hierachical sol= ution > > using a zone precomputation based on static information and then refini= ng > > the path using dynamic information. > > Zone were built using seed/growing system. > > > > Cedric > > > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > > > On 11/28/06, Alias=99 < aliasrob@...> wrote: > > > > > Hi guys, > > > > > > I'm currently working on some 2d grid based pathfinding stuff, and I'= m > > > a little unsatisfied with the performance of A*. It seems to take a v= ery > > > brute force approach to the problem, and is constantly causing CPU is= sues. > > > > > > Are there any more elegant/modern algorithms which have been develope= d > > > which might fit my purposes? I'm just looking to find a simple path b= etween > > > to points, avoiding obstacles. Grid squares are either empty or solid= . > > > > > > Any pointers would be much appreciated, > > > > > > Cheers, > > > Alias > > > > > > > > > =  > > > Take Surveys. Earn Cash. Influence the Future of IT > > > Join SourceForge.net's Techsay panel and you'll get the chance to > > > share your > > > opinions on IT & business topics through brief surveys  and earn cas= h > > > > > > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CI= D=3DDEVDEV > > > > > > _______________________________________________ > > > GDAlgorithmslist mailing list > > > GDAlgorithmslist@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > > > > > > > > =  > > Take Surveys. Earn Cash. Influence the Future of IT > > Join SourceForge.net's Techsay panel and you'll get the chance to share > > your > > opinions on IT & business topics through brief surveys  and earn cash > > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID= =3DDEVDEV > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > 
From: <aliasrob@gm...>  20061128 03:11:19

Hi Tony, I have considered this approach  however, I'm not entirely sure how I'd trace the path from larger clusters to the smaller, more complex areas     B   A    C   Say node A is a larger cluster of 4 identical cells. When I'm traversing that square, do I just assume that the path would go through the centre, and list each adjacent cell in an array or something? Currently the algorithm just uses a set of x y coordinates to address each node, so when expanding a cell it looks to n1 and n+1 to find neighbour cells. I could change this though. Am I along the right lines with this? Cheers, Alias On 28/11/06, Tony Cox <tonycox@...> wrote: > > Another approach is to preprocess the grid by coalescing clusters of > cells which have the same traversability characteristics, to form a much > simpler graph to perform the A* algorithm on. > > Depending on how good your lowlevel "tactical" path following is (i.e. > how to the units actually maneuver the path once computed), you probably > need to impose a condition like convexity on the clusters in order that the > path you generate is easy to navigate. > > One way to do this is to floodfill connected regions with identical > properties (e.g. traversable versus nontraversable, or whatever you > have), and then compute a dissection of each region into convex pieces ( > e.g. Delaunay triangulation). > > A nice property of this approach is that by coalescing homogenous regions > the resolution of the grid doesn't affect the size of the graph, the graph > just reflects the actual complexity of the geometry. > > You can precompute the simplified graph offline, but it's actually not > too expensive to just do it at load time. If you have to cope with a > changing grid, there are ways to cope with incremental changes to > subregions  we had to do this on Dungeon Keeper (circa 1996!), but with > modern processor speeds it might not be necessary (just do the full > recompute) unless you have extremely complex maps. > > Tony Cox  Director of Engineering > Microsoft Game Studios > > Original Message > From: gdalgorithmslistbounces@... [mailto: > gdalgorithmslistbounces@...] On Behalf Of > christer_ericson@... > Sent: Monday, November 27, 2006 6:31 PM > To: Game Development Algorithms > Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms > than A*? > > > I'm currently working on some 2d grid based pathfinding stuff, and > > I'm a little unsatisfied with the performance of A*. It seems to > > take a very brute force approach to the problem, and is constantly > > causing CPU issues. > > > > Are there any more elegant/modern algorithms which have been > > developed which might fit my purposes? I'm just looking to find a > > simple path between to points, avoiding obstacles. Grid squares are > > either empty or solid. > > You need to provide more information to get a good answer. For example, > how big is your grid? Do grid cells change status dynamically or is the > map static? What is the cell connectivity? What are your "CPU issues" > and did you implement your A* algorithm in an efficient way? Etc. > > For a small static map you can precompute a twodimensional table that > for entry (A,B), where A represents the start cell and B the end cell, > contains two bits that specify whether to go N, S, E, or W from the > current start cell to end up at a new "start" cell. This solution is > obviously O(1) in terms of speed for finding the next position to go to, > which is hard to beat. > > The only problem is that, while a 20x20 grid takes ~20K of precomputed > data, a 100x100 grid requires ~12MB of precomputed data (if I didn't > get those numbers exactly right, at least you get the idea). > > With more detail, people are more likely to be able to provide an > answer that might be more helpful to you. > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: <aliasrob@gm...>  20061128 03:05:44

Hi Cedric, The grid size will vary, but it is currently around 100x100, and could easily get much larger. Are you talking about precomputing some kind of hierachical tree, like a quadtree or something? I have considered that, but the implementation of A* I'm using is designed for simple grids and I was hoping not to have to rework it. Sounds like an interesting approach though. Cheers, Alias On 28/11/06, C=E9dric CAILLAUD <cedksatria@...> wrote: > > Hi, > > What is the size of your grid ? > I worked on a project where we had some issues with pathfinding > performances on large grids. Then AI guys implemented a hierachical solut= ion > using a zone precomputation based on static information and then refining > the path using dynamic information. > Zone were built using seed/growing system. > > Cedric > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > On 11/28/06, Alias=99 < aliasrob@...> wrote: > > > Hi guys, > > > > I'm currently working on some 2d grid based pathfinding stuff, and I'm = a > > little unsatisfied with the performance of A*. It seems to take a very = brute > > force approach to the problem, and is constantly causing CPU issues. > > > > Are there any more elegant/modern algorithms which have been developed > > which might fit my purposes? I'm just looking to find a simple path bet= ween > > to points, avoiding obstacles. Grid squares are either empty or solid. > > > > Any pointers would be much appreciated, > > > > Cheers, > > Alias > > > > > > =  > > Take Surveys. Earn Cash. Influence the Future of IT > > Join SourceForge.net's Techsay panel and you'll get the chance to share > > your > > opinions on IT & business topics through brief surveys  and earn cash > > > > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID= =3DDEVDEV > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > > > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > 
From: <aliasrob@gm...>  20061128 03:04:35

Hi Christer, Sure! OK:  Grid varies between 100x100 to I'd say 500x500 max.  Map is completely static  CPU issues are that the algorithm is locking up when looking through longer paths  My implementation might not be that efficient, and I am currently reworking it for efficiency, however I'm wondering if A* is the right approach for this particular problem. Basically, the issue is that my grid may be way too large for a straightforward A* implementation, so I think I need to look at alternatives. Cheers, Alias On 28/11/06, christer_ericson@... < christer_ericson@...> wrote: > > > I'm currently working on some 2d grid based pathfinding stuff, and > > I'm a little unsatisfied with the performance of A*. It seems to > > take a very brute force approach to the problem, and is constantly > > causing CPU issues. > > > > Are there any more elegant/modern algorithms which have been > > developed which might fit my purposes? I'm just looking to find a > > simple path between to points, avoiding obstacles. Grid squares are > > either empty or solid. > > You need to provide more information to get a good answer. For example, > how big is your grid? Do grid cells change status dynamically or is the > map static? What is the cell connectivity? What are your "CPU issues" > and did you implement your A* algorithm in an efficient way? Etc. > > For a small static map you can precompute a twodimensional table that > for entry (A,B), where A represents the start cell and B the end cell, > contains two bits that specify whether to go N, S, E, or W from the > current start cell to end up at a new "start" cell. This solution is > obviously O(1) in terms of speed for finding the next position to go to, > which is hard to beat. > > The only problem is that, while a 20x20 grid takes ~20K of precomputed > data, a 100x100 grid requires ~12MB of precomputed data (if I didn't > get those numbers exactly right, at least you get the idea). > > With more detail, people are more likely to be able to provide an > answer that might be more helpful to you. > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Tony Cox <tonycox@mi...>  20061128 02:53:24

Another approach is to preprocess the grid by coalescing clusters of cells= which have the same traversability characteristics, to form a much simpler= graph to perform the A* algorithm on. Depending on how good your lowlevel "tactical" path following is (i.e. how= to the units actually maneuver the path once computed), you probably need = to impose a condition like convexity on the clusters in order that the path= you generate is easy to navigate. One way to do this is to floodfill connected regions with identical proper= ties (e.g. traversable versus nontraversable, or whatever you have), and t= hen compute a dissection of each region into convex pieces (e.g. Delaunay t= riangulation). A nice property of this approach is that by coalescing homogenous regions t= he resolution of the grid doesn't affect the size of the graph, the graph j= ust reflects the actual complexity of the geometry. You can precompute the simplified graph offline, but it's actually not to= o expensive to just do it at load time. If you have to cope with a changing= grid, there are ways to cope with incremental changes to subregions  we = had to do this on Dungeon Keeper (circa 1996!), but with modern processor s= peeds it might not be necessary (just do the full recompute) unless you hav= e extremely complex maps. Tony Cox  Director of Engineering Microsoft Game Studios Original Message From: gdalgorithmslistbounces@... [mailto:gdalgorithms= listbounces@...] On Behalf Of christer_ericson@...= on.sony.com Sent: Monday, November 27, 2006 6:31 PM To: Game Development Algorithms Subject: Re: [Algorithms] Pathfinding in a 2d grid  better algorithms than= A*? > I'm currently working on some 2d grid based pathfinding stuff, and > I'm a little unsatisfied with the performance of A*. It seems to > take a very brute force approach to the problem, and is constantly > causing CPU issues. > > Are there any more elegant/modern algorithms which have been > developed which might fit my purposes? I'm just looking to find a > simple path between to points, avoiding obstacles. Grid squares are > either empty or solid. You need to provide more information to get a good answer. For example, how big is your grid? Do grid cells change status dynamically or is the map static? What is the cell connectivity? What are your "CPU issues" and did you implement your A* algorithm in an efficient way? Etc. For a small static map you can precompute a twodimensional table that for entry (A,B), where A represents the start cell and B the end cell, contains two bits that specify whether to go N, S, E, or W from the current start cell to end up at a new "start" cell. This solution is obviously O(1) in terms of speed for finding the next position to go to, which is hard to beat. The only problem is that, while a 20x20 grid takes ~20K of precomputed data, a 100x100 grid requires ~12MB of precomputed data (if I didn't get those numbers exactly right, at least you get the idea). With more detail, people are more likely to be able to provide an answer that might be more helpful to you. Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: <christer_ericson@pl...>  20061128 02:30:46

> I'm currently working on some 2d grid based pathfinding stuff, and > I'm a little unsatisfied with the performance of A*. It seems to > take a very brute force approach to the problem, and is constantly > causing CPU issues. > > Are there any more elegant/modern algorithms which have been > developed which might fit my purposes? I'm just looking to find a > simple path between to points, avoiding obstacles. Grid squares are > either empty or solid. You need to provide more information to get a good answer. For example, how big is your grid? Do grid cells change status dynamically or is the map static? What is the cell connectivity? What are your "CPU issues" and did you implement your A* algorithm in an efficient way? Etc. For a small static map you can precompute a twodimensional table that for entry (A,B), where A represents the start cell and B the end cell, contains two bits that specify whether to go N, S, E, or W from the current start cell to end up at a new "start" cell. This solution is obviously O(1) in terms of speed for finding the next position to go to, which is hard to beat. The only problem is that, while a 20x20 grid takes ~20K of precomputed data, a 100x100 grid requires ~12MB of precomputed data (if I didn't get those numbers exactly right, at least you get the idea). With more detail, people are more likely to be able to provide an answer that might be more helpful to you. Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: <cedksatria@gm...>  20061128 02:09:46

Hi, What is the size of your grid ? I worked on a project where we had some issues with pathfinding performance= s on large grids. Then AI guys implemented a hierachical solution using a zon= e precomputation based on static information and then refining the path using dynamic information. Zone were built using seed/growing system. Cedric =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D On 11/28/06, Alias=99 <aliasrob@...> wrote: > > Hi guys, > > I'm currently working on some 2d grid based pathfinding stuff, and I'm a > little unsatisfied with the performance of A*. It seems to take a very br= ute > force approach to the problem, and is constantly causing CPU issues. > > Are there any more elegant/modern algorithms which have been developed > which might fit my purposes? I'm just looking to find a simple path betwe= en > to points, avoiding obstacles. Grid squares are either empty or solid. > > Any pointers would be much appreciated, > > Cheers, > Alias > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share > your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D= DEVDEV > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 > > 
From: <aliasrob@gm...>  20061128 01:19:23

Hi guys, I'm currently working on some 2d grid based pathfinding stuff, and I'm a little unsatisfied with the performance of A*. It seems to take a very brute force approach to the problem, and is constantly causing CPU issues. Are there any more elegant/modern algorithms which have been developed which might fit my purposes? I'm just looking to find a simple path between to points, avoiding obstacles. Grid squares are either empty or solid. Any pointers would be much appreciated, Cheers, Alias 
From: Thatcher Ulrich <tu@tu...>  20061125 14:25:41

On 11/7/06, Nils Pipenbrinck <n.pipenbrinck@...> wrote: > James Milne schrieb: > > Nothing in computational geometry is ever easy :) > > > Oh so true... > > The GLU tesselator has been pretty well shaken down, so giving it a > > whirl first is probably a good idea. We were using that until > > recently at my present employer. We ditched it because we needed to a > > support platform that gave us the opportunity for aggressive multi > > threading, and GLU tesselator didn't support that. The tesselator API > > means you can only use one instance at a time within a single process. > > > > That's one of the reasons why I suggested to take the code and get rid > of the the callback interface. Afterwards the code is entirely > threadsave. I think with some changes in the priority queue it would > even be no big deal to add further multithreading (it's just a simple > sort after all). Also pooling the allocations and inlining a hand full > of little but often called functions gives a performance increase of > about 10 or so. :) > > Oh well, I've digged deep into that code. The code style is horrible at > places, but it's a solid implementation. I wasn't able to break it with > bad data, even if I tried to. > > Btw, I always get my wtf moment when I see performance shootouts of > different tesselators. I've anything I could get my hands on, and most > of them spend 90% of their time in malloc/free. What tesselator shootouts have you seen? Anything other than http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html and the FIST paper? I have a very backburner project to set up a fair tesselator shootout. For the OP, I agree that GLU is a good place to start. I spent some time implementing a FISTlike triangulator, for gameswf, and ran into a lot of trouble with tricky degenerate cases that aren't fully spelled out in the paper. I took another stab at an earclipping triangulator, simplifying some of the steps, and ended up with this code: http://tutestbed.cvs.sourceforge.net/tutestbed/tutestbed/base/ear_clip_triangulate_impl.h?view=markup It's relatively simple and relatively fast, according to some basic measurements. It handles coincident verts and islands and holes, but is not designed to deal with significant selfintersections (i.e. doesn't try to implement the oddeven rule). (It doesn't hang on such input, but the output is probably not what you want.) Thatcher 
From: Jon Watte <hplus@mi...>  20061123 19:28:34

As long as the noise function you base your texture generation on is seamless across those dimensions, the generated texture will seamlessly tile. Thus, if you want a 256x128 texture, generate a 256x128 seamless noise basis function (and 128x64 and smaller, for largerscale features), and feed that through your color generation function. If you don't want to use Perlin noise, you can instead generate highfrequency noise (rand() style) into a 256x128 array, for your highest octave, and then run successive Gaussian filtering passes to generate the lower frequencies. To make it tile seamlessly, all you have to do is "wrap" when you sample neighbors. For powers of two: float neighbor_sample(SampleArray const & array, int x, int y, int dx, int dy) { return return array[(x + dx) & (array.xsize1), (y + dy) & (array.ysize1)]; } Cheers, / h+ Jose Marin wrote: > My problem is how to create textures (using some noise > function, or Worley cellular, or other technique) that > are seamless, on some particular dimension. > > > For example, I need to create textures of sizes like > 128X128, 256X512, etc. > > > I've seen several softwares, like Genetica, that > generates good seamless textures. > >  Jon Watte <hplus@...> escreveu: > > >> I think your question is this: >> >> "I already have a seamless noise function. Now, how >> do I turn this into >> textures that people will want to look at?" >> >> This is as much an art as a science. You have to >> start experimenting, >> and looking at existing procedural texturing >> techniques, such as found >> in the POVRay raytracer language (free download), >> or the Renderman >> shading language (examples exist on the web). Then >> figure out how you >> can modify those techniques to run in hardware >> shaders. >> >> There's no paper on how to do it, much like there is >> no paper on "how to >> compose good music." There is, however, general >> theory, which isn't that >> different from procedural texturing vs general art >> creation in general. >> >> The typical uses for noise are: >> 1) mapping noise values to a color ramp or other >> lookup table. Vary the >> noise shape and octaves to get different looks. >> 2) using 3D noise as a peturbation vector, adding >> turbulence to an >> existing image. >> 3) using limiting, scaling, and thresholding to >> shape the noise; for >> example, you can make nice, blobby, bacterialooking >> patterns this way. >> 4) using noise to scatter/place various primitives, >> such as fuzzy dots >> or lines. >> >> The typical turbulent wood is based on a cylinder >> function that wraps >> (sawtooth style) from the center of the "trunk," >> mapping to a color ramp >> that's yellowtobrown. Add largescale turbulence >> to the lookup >> function for the concentric cylinders, to add >> variation to the wood >> "grain," and add small thresholded specks of noise >> to the output >> function to add the finer texture of the wood. >> >> Cheers, >> >> / h+ >> >> Jose Marin wrote: >> >>> Hi. >>> >>> I've searched for how to generate seamless noise >>> (Google, Yahoo). >>> >>> The problem is that I have found nothing on how to >>> generate seamless textures using Worley cellular >>> >> or >> >>> Perlin noise. >>> >>> Is there some paper on how to do this? >>> >>> Thanks! >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> > _______________________________________________________ > >>> Você quer respostas para suas perguntas? Ou você >>> >> sabe muito e quer compartilhar seu conhecimento? >> Experimente o Yahoo! Respostas ! >> >>> http://br.answers.yahoo.com/ >>> >>> >>> >  > >>> Take Surveys. Earn Cash. Influence the Future of >>> >> IT >> >>> Join SourceForge.net's Techsay panel and you'll >>> >> get the chance to share your >> >>> opinions on IT & business topics through brief >>> >> surveys  and earn cash >> > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > >>> _______________________________________________ >>> GDAlgorithmslist mailing list >>> GDAlgorithmslist@... >>> >>> > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > >>> Archives: >>> >>> > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > >>> >>> >> >  > >> Take Surveys. Earn Cash. Influence the Future of IT >> Join SourceForge.net's Techsay panel and you'll get >> the chance to share your >> opinions on IT & business topics through brief >> surveys  and earn cash >> >> > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > >> _______________________________________________ >> GDAlgorithmslist mailing list >> GDAlgorithmslist@... >> >> > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > >> Archives: >> >> > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > _______________________________________________________ > Yahoo! Acesso Grátis  Internet rápida e grátis. Instale > o discador agora! > http://br.acesso.yahoo.com > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get the chance to share your > opinions on IT & business topics through brief surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > 
From: Alen Ladavac <alenlml@cr...>  20061123 18:14:04

> in the context of engine development, would it make sense to simply drop > scale from the transformation pipeline, and keep scaling effects as an > exception ( perhaps as a "deformer" or mesh animation ) ? A middleground solution is to keep the stretch (sans shear, just the xyz stretch as 3 floats), but only at the top level (permodel), i.e. not to allow the bones to change their stretch in the animation. It is much simpler to maintain and gives you a lot of bang per buck. While animatable perbone stretch does have its uses, for a majority of games it is probably not needed. One thing that we often find very useful, is to allow the stretch to be negative along some axes. This gives you mirrored models which are often needed in the architecture. You just have to be careful to flip the "frontfacedness" flag of the gfx system before you enter the model's rendering if sgn(x*y*z)<0, and you have to also be careful with the front facedness of such flipped models for collision, raycasting and similar. By allowing nonuniform scales, you will probably notice some problems (maybe with lighting, as Tom mentioned), but also with some animations not matching exactly, and most probably with some collision primitives not being able to apply such transform (i.e. a sphere stretched nonuniformly will become an ellipsoid, and a capsule will become eh... elipsoidally capped elliptic prism??? :/ ). In any case, if the nonuniformness is limited to be in a reasonable range (e.g. +/10%?), you can probably just safely ignore the problems. A slightly nonmatching collision primitive or just a bit off lighting are not going to be noticeable. In any way, you probably don't want to stretch your characters nonuniformly too much, because a difference between a chubby dwarf and a slender basketball player is not just a stretch anyway. So the nonuniformity will be mostly just providing for small diversities (see Robert's response). Cheers, Alen 
From: Jose Marin <jose_marin2@ya...>  20061123 14:59:12

Yes, indeed! I missed that! Thanks for the tip!  Paul_Firth@... escreveu: > gdalgorithmslistbounces@... > wrote on 23/11/2006 > 13:46:37: > > > My problem is how to create textures (using some > noise > > function, or Worley cellular, or other technique) > that > > are seamless, on some particular dimension. > > > > > > For example, I need to create textures of sizes > like > > 128X128, 256X512, etc. > > > > That link i posted shows exactly how to do it... > > Cheers, Paul. > > ********************************************************************** > This email and any files transmitted with it are > confidential and > intended solely for the use of the individual or > entity to whom they > are addressed. If you have received this email in > error please notify > postmaster@... > > This footnote also confirms that this email message > has been checked > for all known viruses. > > ********************************************************************** > Sony Computer Entertainment Europe > > >  > Take Surveys. Earn Cash. Influence the Future of IT > Join SourceForge.net's Techsay panel and you'll get > the chance to share your > opinions on IT & business topics through brief > surveys  and earn cash > http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > _______________________________________________________ Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu celular. Registre seu aparelho agora! http://br.mobile.yahoo.com/mailalertas/ 