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

_{Feb}

_{Mar}

_{Apr}

_{May}
(5) 
_{Jun}
(10) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}


2004 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2006 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}
(7) 
2007 
_{Jan}
(2) 
_{Feb}
(4) 
_{Mar}
(1) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(1) 
_{Aug}
(13) 
_{Sep}
(5) 
_{Oct}
(5) 
_{Nov}
(6) 
_{Dec}
(1) 
2008 
_{Jan}
(3) 
_{Feb}
(6) 
_{Mar}
(27) 
_{Apr}
(19) 
_{May}
(9) 
_{Jun}
(4) 
_{Jul}
(25) 
_{Aug}
(12) 
_{Sep}
(13) 
_{Oct}
(9) 
_{Nov}
(21) 
_{Dec}
(35) 
2009 
_{Jan}
(8) 
_{Feb}
(14) 
_{Mar}
(15) 
_{Apr}
(24) 
_{May}
(38) 
_{Jun}
(18) 
_{Jul}
(22) 
_{Aug}
(9) 
_{Sep}
(2) 
_{Oct}
(1) 
_{Nov}

_{Dec}
(11) 
2010 
_{Jan}
(5) 
_{Feb}
(3) 
_{Mar}
(3) 
_{Apr}
(1) 
_{May}
(2) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 





1

2

3

4

5

6

7

8

9

10

11
(1) 
12

13

14

15

16

17

18

19

20

21

22

23
(4) 
24

25

26

27

28

29

30

31

From: Toby Woodwark <zirtix@so...>  20030523 23:37:41

There is now a copy of the Sulk tree in the Sourceforge cvs. Those of you on the SF team, sorry, but you can't commit anything yet! I'd like to review your first couple of patches so I can be sure you won't break anything. Also to point out any style differences, spelling errors, that kind of thing... you get the picture. I'm being anal. To get a copy of the tree you can do: $ cvs d:pserver:anonymous@...:/cvsroot/sulk checkout unstable Or read the cvs instructions at Sourceforge. Toby  "Why is the alphabet in that order? Is it because of that song?"  Steven Wright 
From: Robert Mark Waugh <robert@wa...>  20030523 21:49:22

>Welcome to the list. Glad to see someone's interested in unsucking the >pathfinding code. > > Glad to be here. I'm doing a degree in AI, languages, probablistic computing, and parallel computation so it's right up my alley. >>The lowest cost of all available next steps is expanded >>until the solution is found. This has been proven to be an optimal >>pathfinding algorithm. >> >> > >I'm not sure I completely understand the A* algorithm. > > Unfortunately the way I've stated it it's impossible to fully understand because I made a major mistake. The key is to find a heuristic that never *overestimates* the distance. First, there is the theory in pathfinding that the bigger the distance you can safely say the end is without making an overestimate the better you are going to do in finding a shortest path without looking at all paths in the tree. It's actually a pretty natural way of doing things. Really a breadth first is a naive form of A*. Under the hood they are exactly the same. The key to a breadth first family of shortest paths is the heuristic function I mentioned that estimates the next best possible path. In the naive breadth first search, the easiest way to not overestimate the distance from the current branch to the root is to always say that the end can only be at least one step away (ie, it is one step or more away from where we are). I'll get back to the implications of this in a moment. So, by picking a heuristic that makes the minimum number of steps away we are from the end bigger we can improve the efficiency of the search by eliminating branches of the tree that are most likely not along the path. With a perfect heuristic you would always pick the shortest path without making any wrong guesses at all. We can't do that, though, but we can do better than saying that the end is a minimum of 1 step away. The key is the minimum priority queue. It is a data structure that will return the smallest of whatever attribute you want out of the queue. In this case we are looking for the square with smallest minimum distance away from the end. In your breadth first search, you have a simple First in First Out queue because the distances involved are "current distance away + 1" for all squares. What we need is a slighlty different type of queue though. This is generally done with a heap if you don't need to change the distances (which we should not need to). I couldn't imagine that Python doesn't have a heap available somewhere, but if not I can through one together. It's a very simple data structure. So, to summarize, the A* algorithm is a breadth first search where the choice of the next square to look at is determined by picking the square the with minimum possible distance from the end. The general heuristic used for this sort of application would be linear distance (in this case what's called Manhattan block distance ... ie, 5 up, 3 right is a minimum of 8 moves) plus the predecessor on the path's distance from the start. I hope that I've made it a little bit clearer, although I'm afraid that I've made it more muddled. > Yes, that's better. Hard to get much better than close to optimal. :) > I'm not sure how 'queue' is being used here. Have you left a line out? The minimum queue is the data structure that I mentioned which returns the smallest of all elements stored in it (where smallest is determined by comparing some attribute, in this case minimum possible distance from the end). >Not too big a deal. Copying the whole map is impossible with the >current state of things, because the map objects are too heavily >involved with the drawing code. > > Well, it is possible to do attributed view objects that lay ontop of the map. I'm just not entirely familiar with your ideas of how to build the object model since I just took a look at Sulk a few days ago. > >Ultimately we'll want to have AI in a separate thread along with the >networking code, I imagine. That will at least take lag out of the user >interface: i.e. the SDL mainloop can run simultaneously with pathfinding >and socket I/O. > I agree. The interface should be responsive and IO events should be queued for processing whether it comes from a locally attached channel or from the network. >To sum up, if you can make a patch then go ahead. The heuristic >evaluation of a square at the moment takes place in the middle of >src/players/ai0/UIinput.py, in the parts flagged HEURISTIC. They are >quite simple; for example if 'square.piece' evaluates to True ('square' >is occupied) the score is increased by 1, high scores being bad. I >imagine the score as being an approximate guess at the number of APs it >will take to traverse the route. > > I can provide a patch for the simple breadth first search most readily. I haven't written the A* stuff yet because I noticed it did require futzing with UIinput.py a bit. Perhaps it would be useful to have the source checked into CVS so committing changes doesn't require patching... robert 
From: Toby Woodwark <zirtix@so...>  20030523 20:06:56

On Fri, 20030523 at 04:20, Robert Mark Waugh wrote: > Hello, Welcome to the list. Glad to see someone's interested in unsucking the pathfinding code. I've commented on your bug at SF. Fair comment on the algorithm, and having a temporary patch will make the next (bugfix) release of Sulk less sucky. ... > The lowest cost of all available next steps is expanded > until the solution is found. This has been proven to be an optimal > pathfinding algorithm. I'm not sure I completely understand the A* algorithm. > The added benefit to doing this would be removing the need to compute a > list of all possible shortest routes and then applying the heuristics > afterwards. This method would then return a single shortest path in a > close to optimal amount of time. Yes, that's better. > So, the basic algorithm would work like this (in a rough pseudocode): > > determineShortestPath(Square origin, Square destination, Player player): > squaresToReset = [] > queue = minimumPriorityQueue(origin) > while queue not empty: > currentSquare = queue.dequeueMinimum() > for neighbor in currentSquare.neighbors(): > neighbor.setPrior(currentSquare) > pathCost = currentSquare.getPathCost() +\ > player.moveCost(neighbor) +\ > distance(neighbor, destination) > neighbor.setPathCost(pathCost) > squaresToReset.append(neighbor) > shortestPath = [] > backtrackSquare = destination > while backtrackSquare not None: > shortestPath.prepend(backtrackSquare) > backtrackSquare = backtrackSquare.getPrior() > reset(squaresToReset) > return shortestPath I'm not sure how 'queue' is being used here. Have you left a line out? > A few notes: > In the absolute worst case this algorithm will perform as bad as a > breadth first search, which is what we have now. Nice. > Reseting of the > squares visited adds a minor amount of cost (basically clearing out the > pathcost attribute and the prior attribute). This can be avoided by > making copies or representations of the map that are discarded with each > use. It depends on if you mind polluting the Square object with path > finding attributes. Not too big a deal. Copying the whole map is impossible with the current state of things, because the map objects are too heavily involved with the drawing code. > Anyway, let me know what you guys think. With a tweak in the path > finding algorithm it runs much faster and is actually playable with the AI. That's good. Ultimately we'll want to have AI in a separate thread along with the networking code, I imagine. That will at least take lag out of the user interface: i.e. the SDL mainloop can run simultaneously with pathfinding and socket I/O. To sum up, if you can make a patch then go ahead. The heuristic evaluation of a square at the moment takes place in the middle of src/players/ai0/UIinput.py, in the parts flagged HEURISTIC. They are quite simple; for example if 'square.piece' evaluates to True ('square' is occupied) the score is increased by 1, high scores being bad. I imagine the score as being an approximate guess at the number of APs it will take to traverse the route. Toby  Watch out for the gypsy children in electric dresses they're insane I hear they live in crematoriums and smoke your remains 
From: Robert Mark Waugh <robert@wa...>  20030523 01:26:29

Hello, I posted a new bug describing in brief a solution to the slowness of the path finding algorithm. However I think that the path finding algorithm can be greatly improved by implementing an A* path finding algorithm. Basically, the A* path finding algorithm uses a heuristic function to determine the minimal cost for reaching the desired destination via a next step. The lowest cost of all available next steps is expanded until the solution is found. This has been proven to be an optimal pathfinding algorithm. The problem comes in picking a good heuristic function for estimating the cost for reaching the destination. Generally it is easiest to pick a heuristic function which will always underestimate the cost. One such simple method for doing this is taking the cost thus far and adding it to the Manhattan distance from the pathstep under consideration. Because the minimum distance to arrive at a destination on a grid is a set of two perpendicular lines, this works well as a constant time heuristic function. The nice thing about this, though, is that you can throw in additional heuristics. In this case it would make sense to add in the AP path cost for making the next step. It would be good if the path finding function would take a player object as an agrument, and the player object have a method that would return the path cost for particular types of paths (which would allow for player objects to vary the path cost for different terrain types between player objects and/or states). The added benefit to doing this would be removing the need to compute a list of all possible shortest routes and then applying the heuristics afterwards. This method would then return a single shortest path in a close to optimal amount of time. So, the basic algorithm would work like this (in a rough pseudocode): determineShortestPath(Square origin, Square destination, Player player): squaresToReset = [] queue = minimumPriorityQueue(origin) while queue not empty: currentSquare = queue.dequeueMinimum() for neighbor in currentSquare.neighbors(): neighbor.setPrior(currentSquare) pathCost = currentSquare.getPathCost() +\ player.moveCost(neighbor) +\ distance(neighbor, destination) neighbor.setPathCost(pathCost) squaresToReset.append(neighbor) shortestPath = [] backtrackSquare = destination while backtrackSquare not None: shortestPath.prepend(backtrackSquare) backtrackSquare = backtrackSquare.getPrior() reset(squaresToReset) return shortestPath A few notes: In the absolute worst case this algorithm will perform as bad as a breadth first search, which is what we have now. Reseting of the squares visited adds a minor amount of cost (basically clearing out the pathcost attribute and the prior attribute). This can be avoided by making copies or representations of the map that are discarded with each use. It depends on if you mind polluting the Square object with path finding attributes. Anyway, let me know what you guys think. With a tweak in the path finding algorithm it runs much faster and is actually playable with the AI. robert 
From: Toby Woodwark <zirtix@so...>  20030511 21:17:00

Noone else should get this.  Toby Woodwark <zirtix@...> 