AI Pathfinding

[GoogleCodeExporter]

We need a function that takes start, end and blocking args, that calculates
paths.
blocking with be an [x][y] grid of True/False (True if blocking) values.
It needs to be pseudo random, so, one thing that could be done is have a
class that stores the grid (and then gets updated when it changes, and
pre-calculates each possible path.
Possible paths are any that go from start to end without crossing any
blocking tiles or the same tile twice.

Original issue reported on code.google.com by RoeB...@gmail.com on 26 Apr 2009 at 8:29

[GoogleCodeExporter]

Original comment by RoeB...@gmail.com on 26 Apr 2009 at 9:04

[GoogleCodeExporter]

Original comment by RoeB...@gmail.com on 26 Apr 2009 at 9:23

[GoogleCodeExporter]

I committed a functional pathfinding function in misc.py. Right now it only 
grabs the 
one path, and I think there is a small bug somewhere because one of the test 
cases 
looks a little un-optimized. There are a bunch of notes in the function doc 
string 
and as we get a little more implementation going I can update the function to 
provide 
multiple paths in the most efficient way we decide on.

Check out the pathing test cases by running misc.py in a console.

Original comment by kee...@gmail.com on 27 Apr 2009 at 9:37

• Changed state: Started

[GoogleCodeExporter]

Hmm, well, the randomness will be pretty simple (like you said, just add a 
random
weight to some nodes to throw it off), but another thing, the bugs should try to
avoid lots of towers, so like, I dunno how you would/could do it fast, I was 
thinking
counting the number of towers in (x) range for each path point, perhaps this 
could be
at movement time (and force a recalc...), I dunno...

Original comment by RoeB...@gmail.com on 28 Apr 2009 at 6:14

[GoogleCodeExporter]

can just increment the weight in a circle around each tower, degrading over 
time. 
This will make areas with lots of towers much more costly to the algorithm, and 
therefore avoided more.

We will need to change the blocking map info for this from true/false to 
something 
else -- shouldn't really be a problem.

Original comment by kee...@gmail.com on 28 Apr 2009 at 7:56

[GoogleCodeExporter]

I already made it aware of the grids 0=blank, 1=filled but non-blocking, 
2=filled and
blocking...

What else do we need?

Original comment by RoeB...@gmail.com on 28 Apr 2009 at 4:13

[GoogleCodeExporter]

Finished in rev 89
I think maybe some more cleanups and optimizations will be good...

Original comment by RoeB...@gmail.com on 28 Apr 2009 at 8:52

[GoogleCodeExporter]

I think it is done now.

Original comment by RoeB...@gmail.com on 28 Apr 2009 at 10:45

• Changed state: Fixed