civil-devel Mailing List for Civil

On Mon, 2002-02-25 at 06:06, John Eikenberry wrote:
> I'm currently leaning toward something like #2 and .5 sounds like a
> resonable starting point. Though I'm tempted to keep it a bit higher to
> keep more non-0 values on the map longer.

Actually, reading those threads clarified a fuzzy idea I had; you could
alter those based on terrain type.  Highly passable/clear terrain would
have high T, impenetrable terrain would have low T.  So influence spread
might run down roads rapidly, but stop at water.  I think you still need
to maintain D+T<=1, but it doesn't need to be constant.  Calls for
experimentation.

Semi-off-topic:
If you consider the diffusion by itself without fixed-value sources,
influence is conserved if T+D=1 (that is, the influence lost by each hex
exactly equals its contribution to his neighbors).  If T+D<=1, it slowly
drains away as it diffuses; with T+D>1 it still may thin as it spreads
but the total increases.

I'm also not 100% clear how to handle the edge of the board.  Treat them
as fixed at 0?  Not existing at all, increasing D and reducing T for
those hexes?

> As a ending note, I'm currently reading another good archived usenet
> thread on the same site on "Recognizing Strategic Dispositions"... it
> was the thread which the influence map thread forked off. Its long
> (135Kb) and I'm only about 2/3 through it now, but its been an
> interesting read so far. 

Some good stuff.  I like the influence following and bread crumbs stuff,
clever.

- mikee

Jan Ekholm wrote:

> Are the coordinates that the pathfinder uses hex coords or pixel coords?

Hex coords.

> All units and coords that are handled internally are pixel coords, and
> they are converted to/from hex coords when needed.

Just convert the hex to the hex-center pixel for now... but I was
thinking that it might be nice to return a pixel in the center of the
lowest terrain cost triangle or something. Though unless there are a lot
of mixed terrain hexes on the map, this might not be worth the effort.

> I got the impression that the pathfinder uses hex coords? Is this the
> case? A unit that is in hex (0,0) can actually have the real position from
> (0,0) to about (47,47) in pixel coords.
 
It shouldn't make that much difference, the unit could really be
anywhere in the hexes all along the path. The cost is calculated on the
average of the hex's 6 terrains. The algorithm doesn't care how the unit
moves within the hexes. If we really wanted to go for broke we could use
a micro-pathfinder to find the best path pixel-wise through the hex,
though this seems like overkill. 

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

Michael Earl wrote:

> 1) 'Unit field sum'.  You loop through each unit, and apply influence to
> nearby hexes based on their distance from it (or maybe the distance
> squared, or the visibility between the points, and the unit strength?).
> One side is positive, one negative.  Alternately they're different
> scales (doubling the memory); this would allow you to distinguish
> between uninteresting territory (0 control for each side) and contested
> (high control for each side).

This is probably the most straighforward approach. And would make it
easy to test various influence calculations (using the effects of
visibility, terrain, range, etc).

The influence maps this generated would also contain large regions of
0's... particularly on sparsely populated maps. Thus no sense of the
'front' until contact is made. Not sure if this is good or bad at the
moment, just an observation.

> This would be O(n*r^2), where n is the number of units and r is the
> maximum range a unit projects influence at.  Influence is recalulated
> from scratch each turn.

Recalculating from scratch each turn definately makes this simpler, but
at the cost of possibly useful information. Both in terms of capturing
any sense of time in the map and regenerating a map that might be very
similar the one last turn. 
 
> 2) 'Decaying influence blur'.  Essentially, influence flows out from
> units and influenced hexes.  Hexes start at 0 influence.  With each pass
> of the algorythm (probably no more than 1 per turn?), we apply the
> following actions:
> 
> 	a) Any hex having a unit has its influence set to (+ or -) 1.
> 	b) All other hexes are set to D*(old value)+T*(average of
> 							neighbors)
> 
> D is the decay constant, T the transmission constant.  Offhand I think
> this converges/stabilizes if D<=(1-T).  I'm pretty sure it's O(x*y),
> where x and y are the map size.

I like this idea. Performance friendly (builds the map over time) and
captures some time based info. Has the same issue with large
'uninteresting' areas on the map.

> I kind of like #2 with D=T=.5, but have no clear reason for that at this
> time.  For that matter, the two methods may amount to the same thing at
> that point.  Neither deals explicitly with unseen units, either.

I'm not sure how to handle observed vs unobserved units at the moment.
Only calculating based on observed seems less like the computer
cheating, but you lose a lot of information.

I'm currently leaning toward something like #2 and .5 sounds like a
resonable starting point. Though I'm tempted to keep it a bit higher to
keep more non-0 values on the map longer.
 
> I think all this can be done with matrixes (as I said earlier).  Having
> thought about it more, I'm not sure that's a win; in a decent-sized map,
> that matrixes will be mostly 0, and you'll spend a lot of cycles
> multiplying thing by 0 for no good reason.

Another use of matrixes is that if everything is a matrix, its easy to
add them together. It the hex terrain map from the A* was also a matrix,
it would be easy to figure in the influence map into movement costs to
get paths that take more than just terrain into account.

> Ok, I'll stop rambling for the moment.  I ought to go look at that A*
> stuff, been behind on the code and it sounds nifty...

It doesn't have a ton of comments at the moment, but I tried to make the
code at least somewhat self documenting. And there really isn't that
much actual code there to read.

As a ending note, I'm currently reading another good archived usenet
thread on the same site on "Recognizing Strategic Dispositions"... it
was the thread which the influence map thread forked off. Its long
(135Kb) and I'm only about 2/3 through it now, but its been an
interesting read so far. 

http://gameai.com/strat.thread.html

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

Just a quick note... let me digest this a bit more before attempting an
intelligent comment.

I'm glad you thought your last post was unclear... I was assuming my
lack of math knowledge was to blame for my confusion. 

The thread I quoted from in my previous post also had a description, and
QBasic pseudo implementation, of a heat transfer equation that was used
for an influence map. I've read other places that this is also similar
to some sort of electo-magnetic interfererence algorithm. I had
initially thought that numeric-python might fit the algorithm well.

If you're curious, I've made a local copy of the thread and added name
links to the appropriate postings. Here's the links:

http://zhar.net/projects/pygame/influence_map#heat1
http://zhar.net/projects/pygame/influence_map#heat2

Michael Earl wrote:

> Well, I just re-read my last post, and it was really unclear.  I think I
> sort of started in the middle of thinking about that...
> 
> I can think so far of two ways of calculating influence maps.  Probably
> there are more...
> 
> 1) 'Unit field sum'.  You loop through each unit, and apply influence to
> nearby hexes based on their distance from it (or maybe the distance
> squared, or the visibility between the points, and the unit strength?).
> One side is positive, one negative.  Alternately they're different
> scales (doubling the memory); this would allow you to distinguish
> between uninteresting territory (0 control for each side) and contested
> (high control for each side).
> 
> This would be O(n*r^2), where n is the number of units and r is the
> maximum range a unit projects influence at.  Influence is recalulated
> from scratch each turn.
> 
> 2) 'Decaying influence blur'.  Essentially, influence flows out from
> units and influenced hexes.  Hexes start at 0 influence.  With each pass
> of the algorythm (probably no more than 1 per turn?), we apply the
> following actions:
> 
> 	a) Any hex having a unit has its influence set to (+ or -) 1.
> 	b) All other hexes are set to D*(old value)+T*(average of
> 							neighbors)
> 
> D is the decay constant, T the transmission constant.  Offhand I think
> this converges/stabilizes if D<=(1-T).  I'm pretty sure it's O(x*y),
> where x and y are the map size.
> 
> --
> 
> I kind of like #2 with D=T=.5, but have no clear reason for that at this
> time.  For that matter, the two methods may amount to the same thing at
> that point.  Neither deals explicitly with unseen units, either.
> 
> I think all this can be done with matrixes (as I said earlier).  Having
> thought about it more, I'm not sure that's a win; in a decent-sized map,
> that matrixes will be mostly 0, and you'll spend a lot of cycles
> multiplying thing by 0 for no good reason.
> 
> Ok, I'll stop rambling for the moment.  I ought to go look at that A*
> stuff, been behind on the code and it sounds nifty...
> 
> - mikee
> 
> 
> 
> 
> 
> _______________________________________________
> Civil-devel mailing list
> Civ...@li...
> https://lists.sourceforge.net/lists/listinfo/civil-devel

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

Well, I just re-read my last post, and it was really unclear.  I think I
sort of started in the middle of thinking about that...

I can think so far of two ways of calculating influence maps.  Probably
there are more...

1) 'Unit field sum'.  You loop through each unit, and apply influence to
nearby hexes based on their distance from it (or maybe the distance
squared, or the visibility between the points, and the unit strength?).
One side is positive, one negative.  Alternately they're different
scales (doubling the memory); this would allow you to distinguish
between uninteresting territory (0 control for each side) and contested
(high control for each side).

This would be O(n*r^2), where n is the number of units and r is the
maximum range a unit projects influence at.  Influence is recalulated
from scratch each turn.

2) 'Decaying influence blur'.  Essentially, influence flows out from
units and influenced hexes.  Hexes start at 0 influence.  With each pass
of the algorythm (probably no more than 1 per turn?), we apply the
following actions:

	a) Any hex having a unit has its influence set to (+ or -) 1.
	b) All other hexes are set to D*(old value)+T*(average of
							neighbors)

D is the decay constant, T the transmission constant.  Offhand I think
this converges/stabilizes if D<=(1-T).  I'm pretty sure it's O(x*y),
where x and y are the map size.

--

I kind of like #2 with D=T=.5, but have no clear reason for that at this
time.  For that matter, the two methods may amount to the same thing at
that point.  Neither deals explicitly with unseen units, either.

I think all this can be done with matrixes (as I said earlier).  Having
thought about it more, I'm not sure that's a win; in a decent-sized map,
that matrixes will be mostly 0, and you'll spend a lot of cycles
multiplying thing by 0 for no good reason.

Ok, I'll stop rambling for the moment.  I ought to go look at that A*
stuff, been behind on the code and it sounds nifty...

- mikee

John,

Are the coordinates that the pathfinder uses hex coords or pixel coords?
All units and coords that are handled internally are pixel coords, and
they are converted to/from hex coords when needed.

I got the impression that the pathfinder uses hex coords? Is this the
case? A unit that is in hex (0,0) can actually have the real position from
(0,0) to about (47,47) in pixel coords.

-- 
      Real children don't go hoppity-skip unless they are on drugs.
                          -- Susan Sto Helit, in Hogfather (Terry Pratchett)

On Thu, 21 Feb 2002, John Eikenberry wrote:

>Jan Ekholm wrote:
>
>> >    path = Path(scenario.map,((Ax,Ay),(Bx,By)))
>> >
>> >This is a bit cumbersome and could be changed pretty easily to something
>> >like:
>> >
>> >    path = Path((Ax,Ay),(Bx,By))
>> 
>> The former isn't too cumbersome in my opinion. The code would anyway be
>> used in a few selected areas, and one extra parameter (I'll copy'n'paste
>> it from here anyway) doesn't really matter. It might be more general if
>> you can give in the map it should operate on. 
>
>I don't know. How about at least getting rid of one of those sets of
>parens:
>
>    path = Path(scenario.map,(Ax,Ay),(Bx,By))

Hmm, yes, that's better. I didn't see the extra parens in the code above.
I prefer to avoid Lisp:y amounts of parens if possible. :)
 
>> >Then to get the actual path - a list of (x,y) point tuples:
>> >
>> >    for x,y in path.caculate():
>> >        unit.move(x,y)
>> 
>> Yes, this is nice. I like it. Simple, yet very elegant. I'll try to add it
>> in today. It's going to be interesting to see what happens.
>> 
><snip> 
>> Personally I'm not too fond of overloading __call__(). Possibly because
>> I'm not too used with overloading Python operations. Adding it won't hurt,
>> but I'll stick to the path.calculate() version. 
>
>Cool. I already added it, but I might remove it. I'm not going to worry
>about it for now. [shrug]

No, don't remove it. If I don't like it I don't have to use it, there's
always the calculate() method. Someone else (like you) may like the
overloaded method better and use it. Choice is never bad.

-- 

 He says gods like to see an atheist around. Gives them something to aim at.
                                            -- Terry Pratchett, Small Gods

Jan Ekholm wrote:

> >    path = Path(scenario.map,((Ax,Ay),(Bx,By)))
> >
> >This is a bit cumbersome and could be changed pretty easily to something
> >like:
> >
> >    path = Path((Ax,Ay),(Bx,By))
> 
> The former isn't too cumbersome in my opinion. The code would anyway be
> used in a few selected areas, and one extra parameter (I'll copy'n'paste
> it from here anyway) doesn't really matter. It might be more general if
> you can give in the map it should operate on. 

I don't know. How about at least getting rid of one of those sets of
parens:

    path = Path(scenario.map,(Ax,Ay),(Bx,By))
 
> >Then to get the actual path - a list of (x,y) point tuples:
> >
> >    for x,y in path.caculate():
> >        unit.move(x,y)
> 
> Yes, this is nice. I like it. Simple, yet very elegant. I'll try to add it
> in today. It's going to be interesting to see what happens.
> 
<snip> 
> Personally I'm not too fond of overloading __call__(). Possibly because
> I'm not too used with overloading Python operations. Adding it won't hurt,
> but I'll stick to the path.calculate() version. 

Cool. I already added it, but I might remove it. I'm not going to worry
about it for now. [shrug]

> >> You mean my terrain cost map or the one in civil. Mine is a simple list
> >> of lists (x,y) storing terrain costs. I average in all the triangles
> >> into one number.
> >
> >I changed this to a list of arrays. Arrays seem to have faster access
> >and take up less memory. :)
> 
> Interesting. Maybe lists need to be traversed when accessed, and arrays
> can be directly accessed, as in other languages?

I don't know. It didn't make a big difference and maybe none at all (its
hard to tell with random maps). But it does use less memory, with at
least no slowdown.
 
> John, this seems like a very fine addition. I think you've done a very
> excellent job here!

Thanks. Its fun working on AI again. I'm looking forward to getting
started on the influence map. Speaking of which... time to re-read
Mike's email and prepare my barrage of questions.

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

On Thu, 21 Feb 2002, John Eikenberry wrote:

>John Eikenberry wrote:
>
>> > Or a list of path objects to describe a full path? One object contains a
>> > destination, nor much else. A list of these describe how to get to an
>> > ultimate destination through a series of intermediate destinations.
>> > Something like that is what I'd like to use. I could then create a new
>> > type of plan that has such a path instead of a single destination.
>> 
>> At the moment, you create the path object and run the calculate method.
>> It returns the list of points (x,y coords) of the path.
>
>Ok. I've fixed the problem by making the terrain cost map a shared class
>attribute. Time to explain how its used in a bit more detail.
>
>When you have a unit that wants to know how to get from point A to B -
>points being (x,y) tuples. You first create Path instance:
>
>    path = Path(scenario.map,((Ax,Ay),(Bx,By)))
>
>This is a bit cumbersome and could be changed pretty easily to something
>like:
>
>    path = Path((Ax,Ay),(Bx,By))

The former isn't too cumbersome in my opinion. The code would anyway be
used in a few selected areas, and one extra parameter (I'll copy'n'paste
it from here anyway) doesn't really matter. It might be more general if
you can give in the map it should operate on. 

>Then to get the actual path - a list of (x,y) point tuples:
>
>    for x,y in path.caculate():
>        unit.move(x,y)

Yes, this is nice. I like it. Simple, yet very elegant. I'll try to add it
in today. It's going to be interesting to see what happens.

>I kept it in 2 steps so I could add code later to step through the
>pathfinding (find N steps this frame). Which is handy when CPU time is 
>limited. 
>
>Hmm... I could alias __call__ to calculate. That might make the code
>more readable: 
>
>    for x,y in path():
>        unit.move(x,y)
>
>What do you think?

Personally I'm not too fond of overloading __call__(). Possibly because
I'm not too used with overloading Python operations. Adding it won't hurt,
but I'll stick to the path.calculate() version. 

>> You mean my terrain cost map or the one in civil. Mine is a simple list
>> of lists (x,y) storing terrain costs. I average in all the triangles
>> into one number.
>
>I changed this to a list of arrays. Arrays seem to have faster access
>and take up less memory. :)

Interesting. Maybe lists need to be traversed when accessed, and arrays
can be directly accessed, as in other languages?

John, this seems like a very fine addition. I think you've done a very
excellent job here!

-- 

 He says gods like to see an atheist around. Gives them something to aim at.
                                            -- Terry Pratchett, Small Gods

John Eikenberry wrote:

> > Or a list of path objects to describe a full path? One object contains a
> > destination, nor much else. A list of these describe how to get to an
> > ultimate destination through a series of intermediate destinations.
> > Something like that is what I'd like to use. I could then create a new
> > type of plan that has such a path instead of a single destination.
> 
> At the moment, you create the path object and run the calculate method.
> It returns the list of points (x,y coords) of the path.

Ok. I've fixed the problem by making the terrain cost map a shared class
attribute. Time to explain how its used in a bit more detail.

When you have a unit that wants to know how to get from point A to B -
points being (x,y) tuples. You first create Path instance:

    path = Path(scenario.map,((Ax,Ay),(Bx,By)))

This is a bit cumbersome and could be changed pretty easily to something
like:

    path = Path((Ax,Ay),(Bx,By))

Then to get the actual path - a list of (x,y) point tuples:

    for x,y in path.caculate():
        unit.move(x,y)

I kept it in 2 steps so I could add code later to step through the
pathfinding (find N steps this frame). Which is handy when CPU time is 
limited. 

Hmm... I could alias __call__ to calculate. That might make the code
more readable: 

    for x,y in path():
        unit.move(x,y)

What do you think?

> You mean my terrain cost map or the one in civil. Mine is a simple list
> of lists (x,y) storing terrain costs. I average in all the triangles
> into one number.

I changed this to a list of arrays. Arrays seem to have faster access
and take up less memory. :)
  
> > If you need some data in, say, the Unit or Map classes just add it. It's
> > no problem. That's what they are there for. 
> 
> Hmm.... I might add the terrain costs map to the Map class. Could even
> make it a lazy cache that way.

Decided to keep it local for the moment. 

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

Jan Ekholm wrote:

> Nice. :) I think there are a few similar mistakes in my code too that
> cause unnecessary slowdown. Especielly when drawing the map I think there
> are a lot that could be improved using some magical Python functions.

Nice thing about A* is that its a well understood algorithm. Makes it
much easier to notice problems.
 
> Btw. how do I compile the .c file? I haven't used distutils for anything
> own (never done a C extension)?

Copy your python's Makefile.pre.in into the dc_module directory. It can
be found (on debian) at:

/usr/lib/python2.1/config/Makefile.pre.in

Run the command: make -f Makefile.pre.in boot
Then run: make
Copy the dcmodule.so file into the ai directory. 

Not pretty. But that's why the python versions of the algorithms are
there. :)
  
> >You want to use it??? Ok then, it needs a bit more re-structuring before
> >it will be useful. The quicky class wrapper I gave it has a big flaw...
> >The static terrain cost map is generated for each path in the way I had
> >envisioned using it. 
> 
> Sure, why not let the player use the pathfinder is he/she wants? Simpler
> than clicking out a lot of waypoints.

I agree completely.

> >The way I was thinking it could be used was to create a path object for
> >each path, and to delete it when done. I've gotten in the habit of
> >making disposable objects while using Zope, and it seemed appropriate. 
> 
> Or a list of path objects to describe a full path? One object contains a
> destination, nor much else. A list of these describe how to get to an
> ultimate destination through a series of intermediate destinations.
> Something like that is what I'd like to use. I could then create a new
> type of plan that has such a path instead of a single destination.

At the moment, you create the path object and run the calculate method.
It returns the list of points (x,y coords) of the path.

> >I've done several test with this and don't seem to get any speed boost.
> >I think any speed gained was lost in the overhead of the additional code
> >needed for the map version. I had added a line like this:
> >
> >distance_cost_l = map(distance_cost,new_points,[p1 for p in new_points])
> 
> Hmm, you just get another for-loop for feeding the points to map(). I
> can't really think functionally, so I have no idea as to what it actually
> does...
 
I think I could re-structure the code to take better advantage of map().
But I'm thinking enough is enough for now... it seems fast enough.

In python, map() can be faster as it works sort of like an inlined loop.
It only requires locating the C function once and inlines all calls to
it. It can really help in some situations.

> Ok. Currently I think it's no problem if the pathfinding takes some time,
> as long as it stays under 1s or similar. Otherwise the UI starts to feel
> sluggish for players that use the pathfinder for moving units.

There are many other optimizations that can be done, just not in a
general manner. We can easily make A* many times faster. No worries.
 
> Ok. I need to dig into the code a little bit and find out what the terrain
> map actually does. :) 

You mean my terrain cost map or the one in civil. Mine is a simple list
of lists (x,y) storing terrain costs. I average in all the triangles
into one number.
 
> If you need some data in, say, the Unit or Map classes just add it. It's
> no problem. That's what they are there for. 

Hmm.... I might add the terrain costs map to the Map class. Could even
make it a lazy cache that way.

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

On Wed, 20 Feb 2002, John Eikenberry wrote:

>Jan Ekholm wrote:
>
>> Great stuff, John! I tested it a little bit, and it works without any
>> problems. Must remember to add python-pqueue to the list of required
>> modules. Hmm, ok, I did it already. Not that I know if the Debian package
>> building even works anymore (those Debian folks have sure managed to setup
>> a horribly complex system for people attempting to do packages).
>
>Just commited a new version. Should be lots better. Fixed a couple
>stupid mistakes in my implementation resulting in a big speed boost
>(10x) and better paths.

Nice. :) I think there are a few similar mistakes in my code too that
cause unnecessary slowdown. Especielly when drawing the map I think there
are a lot that could be improved using some magical Python functions.

>Thanks for updating the dpkg control file. And yeah its complex, but it
>works well (which is more than I can say about rpm ;).

I don't know wether our debian/ directory is up-to-date anymore, but I
don't care about it until we have something stable that *needs* to be
packaged.

Btw. how do I compile the .c file? I haven't used distutils for anything
own (never done a C extension)?
 
>> Could you help me by describing how to use that classes? Looking at 
>> test_path.py makes it look fairly simple, but I need some help. Typical
>> use would be a unit that wants to move to (x,y), as clicked by the player.
>> How do I get a path from (unitx,unity) to (x,y)? In what format do I get
>> the path? Can I iterate over such a path and draw it piece by piece? 
>
>You want to use it??? Ok then, it needs a bit more re-structuring before
>it will be useful. The quicky class wrapper I gave it has a big flaw...
>The static terrain cost map is generated for each path in the way I had
>envisioned using it. 

Sure, why not let the player use the pathfinder is he/she wants? Simpler
than clicking out a lot of waypoints.

>The way I was thinking it could be used was to create a path object for
>each path, and to delete it when done. I've gotten in the habit of
>making disposable objects while using Zope, and it seemed appropriate. 

Or a list of path objects to describe a full path? One object contains a
destination, nor much else. A list of these describe how to get to an
ultimate destination through a series of intermediate destinations.
Something like that is what I'd like to use. I could then create a new
type of plan that has such a path instead of a single destination.
>> map() seems to be a major speedup, if it can be applied. I tried using it
>> in some places, but it's really a confusing function.
> 
>I've done several test with this and don't seem to get any speed boost.
>I think any speed gained was lost in the overhead of the additional code
>needed for the map version. I had added a line like this:
>
>distance_cost_l = map(distance_cost,new_points,[p1 for p in new_points])

Hmm, you just get another for-loop for feeding the points to map(). I
can't really think functionally, so I have no idea as to what it actually
does...

>That list comprehension plus chaning the for loop to loop over indexes
>used in list lookups - range(len(new_points)) - caused as much as the
>map gained. I tried a few variations on this idea with no luck and
>finally decided it wasn't work the effort. 
>
>The big possible speedup from map would be to move the whole for loop
>into the map call. This would require moving a big chunk into C and
>readability would suffer. I'll do it if performance becomes an issue.

Ok. Currently I think it's no problem if the pathfinding takes some time,
as long as it stays under 1s or similar. Otherwise the UI starts to feel
sluggish for players that use the pathfinder for moving units.

>> >-improve the heuristic
>> 
>> This could actually be data retrieved from the unit itself? Units such as
>> artillery units have a really hard time moving in woods, and can't
>> more at all over rocky terrain, while they can be
>> fast on roads. Infantry can moved even on rocky terrain, although at a
>> reduced speed.
>>  
>> Maybe the unit should have a type specific lookup table for costs for each
>> type of terrain? And some method like:
>> 
>>     class Unit:
>>         ....
>>         def getTerrainCost (self, terraintype):
>>             return self.costs[terraintype]
>
>Hmm... this would make the static terrain map invalid. If this returned
>a terrain cost modifier instead of the terrain cost, I could still use
>the static map and modify it using this value (which could be cached in
>a simple dictionary for speedy lookups).
>
>I'll check again to make sure the static terrain map is helping as much
>as I think it is. I haven't messed with it much since improving the rest
>of the algorithm. ... [time passes] ... Ok. Big difference. Its about
>10x slower without the static terrain map.

Ok. I need to dig into the code a little bit and find out what the terrain
map actually does. :) 

If you need some data in, say, the Unit or Map classes just add it. It's
no problem. That's what they are there for. 

-- 
"It would seem that you have no useful skill or talent whatsoever," he said.
              "Have you thought of going into teaching?"  
                                                    -- Terry Pratchett, Mort

Jan Ekholm wrote:

> Great stuff, John! I tested it a little bit, and it works without any
> problems. Must remember to add python-pqueue to the list of required
> modules. Hmm, ok, I did it already. Not that I know if the Debian package
> building even works anymore (those Debian folks have sure managed to setup
> a horribly complex system for people attempting to do packages).

Just commited a new version. Should be lots better. Fixed a couple
stupid mistakes in my implementation resulting in a big speed boost
(10x) and better paths.

Thanks for updating the dpkg control file. And yeah its complex, but it
works well (which is more than I can say about rpm ;).
 
> Could you help me by describing how to use that classes? Looking at 
> test_path.py makes it look fairly simple, but I need some help. Typical
> use would be a unit that wants to move to (x,y), as clicked by the player.
> How do I get a path from (unitx,unity) to (x,y)? In what format do I get
> the path? Can I iterate over such a path and draw it piece by piece? 

You want to use it??? Ok then, it needs a bit more re-structuring before
it will be useful. The quicky class wrapper I gave it has a big flaw...
The static terrain cost map is generated for each path in the way I had
envisioned using it. 

The way I was thinking it could be used was to create a path object for
each path, and to delete it when done. I've gotten in the habit of
making disposable objects while using Zope, and it seemed appropriate. 

If we stick with this idea, I'll probably make the terrain map into a
class attribute. First time I've ever found a mutable class attribute to
be a useful idea. :)
 
> >My todo for this code is currently:
> >-numeric python version (I'll commit this as soon as it works)
> >-version using map()
> 
> map() seems to be a major speedup, if it can be applied. I tried using it
> in some places, but it's really a confusing function.
 
I've done several test with this and don't seem to get any speed boost.
I think any speed gained was lost in the overhead of the additional code
needed for the map version. I had added a line like this:

distance_cost_l = map(distance_cost,new_points,[p1 for p in new_points])

That list comprehension plus chaning the for loop to loop over indexes
used in list lookups - range(len(new_points)) - caused as much as the
map gained. I tried a few variations on this idea with no luck and
finally decided it wasn't work the effort. 

The big possible speedup from map would be to move the whole for loop
into the map call. This would require moving a big chunk into C and
readability would suffer. I'll do it if performance becomes an issue.

> >-improve the heuristic
> 
> This could actually be data retrieved from the unit itself? Units such as
> artillery units have a really hard time moving in woods, and can't
> more at all over rocky terrain, while they can be
> fast on roads. Infantry can moved even on rocky terrain, although at a
> reduced speed.
>  
> Maybe the unit should have a type specific lookup table for costs for each
> type of terrain? And some method like:
> 
>     class Unit:
>         ....
>         def getTerrainCost (self, terraintype):
>             return self.costs[terraintype]

Hmm... this would make the static terrain map invalid. If this returned
a terrain cost modifier instead of the terrain cost, I could still use
the static map and modify it using this value (which could be cached in
a simple dictionary for speedy lookups).

I'll check again to make sure the static terrain map is helping as much
as I think it is. I haven't messed with it much since improving the rest
of the algorithm. ... [time passes] ... Ok. Big difference. Its about
10x slower without the static terrain map.

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

On Mon, 18 Feb 2002, John Eikenberry wrote:

>
>Ok. I cleaned up the code a bit and finally got it commited. The files
>are all in src/ai and the consist of...
>
>dc_module/Setup.in  
>dc_module/dcmodule.c     -The C versions of the distance cost algorithms.
>distance_cost.py         -Python wrapper and python versions of same.
>basic_path.py            -The current A* algorithm. 
>test_path.py             -The ascii display test code.

Great stuff, John! I tested it a little bit, and it works without any
problems. Must remember to add python-pqueue to the list of required
modules. Hmm, ok, I did it already. Not that I know if the Debian package
building even works anymore (those Debian folks have sure managed to setup
a horribly complex system for people attempting to do packages).

Could you help me by describing how to use that classes? Looking at 
test_path.py makes it look fairly simple, but I need some help. Typical
use would be a unit that wants to move to (x,y), as clicked by the player.
How do I get a path from (unitx,unity) to (x,y)? In what format do I get
the path? Can I iterate over such a path and draw it piece by piece? 

>My todo for this code is currently:
>-numeric python version (I'll commit this as soon as it works)
>-version using map()

map() seems to be a major speedup, if it can be applied. I tried using it
in some places, but it's really a confusing function.

>-improve the heuristic

This could actually be data retrieved from the unit itself? Units such as
artillery units have a really hard time moving in woods, and can't
more at all over rocky terrain, while they can be
fast on roads. Infantry can moved even on rocky terrain, although at a
reduced speed.

Maybe the unit should have a type specific lookup table for costs for each
type of terrain? And some method like:

    class Unit:
        ....
        def getTerrainCost (self, terraintype):
            return self.costs[terraintype]

-- 
      Real children don't go hoppity-skip unless they are on drugs.
                          -- Susan Sto Helit, in Hogfather (Terry Pratchett)

Ok. I cleaned up the code a bit and finally got it commited. The files
are all in src/ai and the consist of...

dc_module/Setup.in  
dc_module/dcmodule.c     -The C versions of the distance cost algorithms.
distance_cost.py         -Python wrapper and python versions of same.
basic_path.py            -The current A* algorithm. 
test_path.py             -The ascii display test code.

My todo for this code is currently:
-numeric python version (I'll commit this as soon as it works)
-version using map()
-improve the heuristic

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

Hi,

I added a first version of an AI debugging layer to the playfield.
Currently when you start the client it will show a number on top of each
hex. The number is (as an example) just the sum of the x and y coordinate.
The value can be easily changed to something meaningful, and the layer
code is extremely simple, see:

	src/playfield/ai_debug_layer.py

To provide some other layers with other info just subclass that layer and
override one method to provide the actual value.

The layer can be toggled on and off with Alt-1. This allows several layers
to be used at the same time, as it's very easy to add another layer that
can be toggled on/off with, say, Alt-2.

As for the messiness of the AI code. Well, just check it in. There's no
other code that uses it yet, so it won't do any harm. :)


-- 
        Five exclamation marks, the sure sign of an insane mind.
                                              -- Terry Pratchett, Reaper Man

On 17 Feb 2002, Michael Earl wrote:

>On Sun, 2002-02-17 at 20:15, John Eikenberry wrote: 
>> This feature would be nice in general for AI development. My little
>> ascii maps have been a big help so far. It'd be very useful if you could
>> modify the display in some way. Like being able to mark each hex in the
>> open set for A* (helpful for optimization), or show the layout of the
>> influence map. Just the ability to change the color of a few pixils in
>> each hex would suffice.
>
>Most likely this could be done with just another layer in the playfield
>display... does the map editor already paint a dot in the center of each
>hex?  Possibly that could be adapted...

Maybe I should lear to read *all* messages before replying... :) Yes, the
map editor does that (see editor/mapview.py:109). I can add such a layer
pretty easily, but it we want to show costs etc I'll need some help.

-- 

        Most gods find it hard to walk and think at the same time.
                                             -- Terry Pratchett, Small Gods

On Sun, 17 Feb 2002, John Eikenberry wrote:

>When I first had the idea, I was thinking of a modifier key as well.
>Shift would make a good default IMO.

Ok, this sounds like a good idea.

>I think I've finally got my sourceforge cvs working. But I really made a
>mess of my code while working on optimizations. I'll get it cleaned up
>and commited by tommorrow (I have the day off :).

I read about that on the pygame list. It sounded a little bit too good at
first.
 
>> I think it would be easier to develop the pathfinder if the paths could be
>> seen on the real map? Some facility for easily reloading the module into a
>> running client could be provided, maybe using reload(), to make debugging
>> and testing easier.
>
>This feature would be nice in general for AI development. My little
>ascii maps have been a big help so far. It'd be very useful if you could
>modify the display in some way. Like being able to mark each hex in the
>open set for A* (helpful for optimization), or show the layout of the
>influence map. Just the ability to change the color of a few pixils in
>each hex would suffice.

I'm not sure what that data would be, so you'll have to help me a little
bit. For debugging we'll just throw in a few extra layers into the
Playfield class that draws the A* related extra data. We can then disable
these layers for the final versions. But as we do have a fairly modular
system it would be a shame not to use it.

-- 

        Most gods find it hard to walk and think at the same time.
                                             -- Terry Pratchett, Small Gods

On Sun, 2002-02-17 at 20:15, John Eikenberry wrote: 
> This feature would be nice in general for AI development. My little
> ascii maps have been a big help so far. It'd be very useful if you could
> modify the display in some way. Like being able to mark each hex in the
> open set for A* (helpful for optimization), or show the layout of the
> influence map. Just the ability to change the color of a few pixils in
> each hex would suffice.

Most likely this could be done with just another layer in the playfield
display... does the map editor already paint a dot in the center of each
hex?  Possibly that could be adapted...

- mikee

Jan Ekholm wrote:

> All this talk about A* on pygame got me thinking about the old discussions
> we had about how the player could use pathfinding in Civil. Currently
> units stumble in a straight line towards the given destination, which
> works quite ok.
> 
> However, it would be nice to let the player also use pathfinding to find a
> faster path, especielly if what matters is hwo fast the unit arrives, and
> not what path it takes. For thos moments when the exact path is important
> the old system would let you plot out the path exactly.
> 
> So, I'd like to integrate John's code and provide an alternate way of
> giving "move" and "movefast" orders that utilize the nice pathfinding
> module (or soon to be module). Maybe have one way be triggered by holding
> down shift, control or something? Ideas for that?

When I first had the idea, I was thinking of a modifier key as well.
Shift would make a good default IMO.

I think I've finally got my sourceforge cvs working. But I really made a
mess of my code while working on optimizations. I'll get it cleaned up
and commited by tommorrow (I have the day off :).
 
> I think it would be easier to develop the pathfinder if the paths could be
> seen on the real map? Some facility for easily reloading the module into a
> running client could be provided, maybe using reload(), to make debugging
> and testing easier.

This feature would be nice in general for AI development. My little
ascii maps have been a big help so far. It'd be very useful if you could
modify the display in some way. Like being able to mark each hex in the
open set for A* (helpful for optimization), or show the layout of the
influence map. Just the ability to change the color of a few pixils in
each hex would suffice.

And the ability to reload while running is always nice.

-- 

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

I added some code last night and today that finally adds movement and
rotation speeds to the units. So far we've used hardcoded speeds along
with a few comments like:

	"TODO: fake values" 

The Unit class now has getMovementSpeed() and getTurningSpeed() methods
that return type-specific speeds. The former method returns a tuple of two
values, one for fast movement, and another for slow movement.

I noticed that plans that are not fully executed during an action phase
get nicely transmitted back to the client/ai players, which is exactly as
intended. 

And so on...

-- 

             Gravity is a habit that is hard to shake off.
                                              -- Terry Pratchett, Small Gods

Phew...

First batch of code for implementing executors and action is in, and works
fairly ok. Lots of bugs, major bugs and buglest probably remain, but the
grunt work is done. 

Please have a look at the new "plan executing" code in engine/executor/. I
think it's a lot simpler than it was before. I moved a lot of common stuff
out into some *_util files in order to get code reuse without inheritance.

In case you feel like testing, only the orders "move" and "rotate" work
yet.

Comments etc are welcome.

-- 
                 "Students?" barked the Archchancellor.
    "Yes, Master. You know? They're the thinner ones with the pale faces?
  Because we're a university? They come with the whole thing, like rats --"
                                         -- Terry Pratchett, Moving Pictures

On Tue, 12 Feb 2002, John Eikenberry wrote:

>Jan Ekholm wrote:

>> Speaking of A*, would you like to check it into CVS? It could be easier
>> for you to handle the source, and thus also have a backup in case of a
>> disaster. I'd put all AI-related things in src/ai/.=20
>
>Need permission. If we're still at sourceforge I created a user there
>not to long ago. What info do you need? Username: zhar

You have it, and have had it for a while already. :)

>> >For the A* I'm mainly just trying to optimize. In my tests with my
>> >current version it takes about 1 second to find a path on a 128x128 map
>> >for paths of ~100 steps. This is with a pre-calculated terrain cost
>> >array and the distance cost code moved into a C library. I'm thinking
>> >about a way I could use python-numeric's matrix processing to do this.
>> >Not sure if it will help, but its worth some thought (and code if I can
>> >figure out a way to do it).
>>=20
>> The good thing now is that the AI is allowed to use more time than befor=
e,
>> as the orders need not be done in realtime anymore. So it's more of a
>> "traditional" AI.=A0I think a minute or a few can be allocated to the AI=
=2E
>> Maybe with a debugging/test option to make it do really quick decisions.
>
>True, but I don't want to burn all my AI cpu time on pathfinding. I'm
>sure I can speed it up some more.

Unfortunately I really suck at optimizing Python code, so I'm not much
help with that. I can do some basic optimizations as described on a few
webpages I know, but Numeric & co are total Black Magic(tm) for me.

--=20
   Kids! Bringing about Armageddon can be dangerous. Do not attempt it in
   your home.
                             -- Terry Pratchett & Neil Gaiman, Good Omens

Jan Ekholm wrote:

> Phew, I must get bored more often, it seems all kinds of goodies start to
> drop in on this list. :)
=20
The timing helps as well... I was bored too. ;)
=20
> On Sat, 9 Feb 2002, John Eikenberry wrote:
>=20
> >I'm slowly hacking on improving the A* and working up an influence map.
> >Having to re-learn a bunch of math... I think I've got partial amnesia,
> >as I can't seem to remember much of anything. :P
>=20
> I think that's a very common phenomenom. I don't remember anything of my
> math I read 5 years ago, although most of it was utterly useless.

Close to around 12 years for me... didn't study it much in college. :P
=20
> Speaking of A*, would you like to check it into CVS? It could be easier
> for you to handle the source, and thus also have a backup in case of a
> disaster. I'd put all AI-related things in src/ai/.=20

Need permission. If we're still at sourceforge I created a user there
not to long ago. What info do you need? Username: zhar

> >For the A* I'm mainly just trying to optimize. In my tests with my
> >current version it takes about 1 second to find a path on a 128x128 map
> >for paths of ~100 steps. This is with a pre-calculated terrain cost
> >array and the distance cost code moved into a C library. I'm thinking
> >about a way I could use python-numeric's matrix processing to do this.
> >Not sure if it will help, but its worth some thought (and code if I can
> >figure out a way to do it).
>=20
> The good thing now is that the AI is allowed to use more time than before,
> as the orders need not be done in realtime anymore. So it's more of a
> "traditional" AI.=A0I think a minute or a few can be allocated to the AI.
> Maybe with a debugging/test option to make it do really quick decisions.

True, but I don't want to burn all my AI cpu time on pathfinding. I'm
sure I can speed it up some more.

> >I'm figuring out numeric to implement influence maps. Not very far on
> >this yet, still figuring out the best way to propogate the values. For
> >anyone not knowing what an influence map is, here's a quote from the
> >influence map thread archived at gameai.com:
> >
> >    You take an array which is the same size of the map and set all
> >    locations to zero.  You then take and place a positive value at each
> >    friendly unit location and a negative value at each enemy unit
> >    location.  You then loop looking at each location of the array and
> >    adjusting the value found there by its neighbors.  (Increase it by
> >    one for each friendly unit and decrease it by one for each enemy
> >    unit.)  Now the computer can tell how much control the two players
> >    had over the board.  The sign of the value indicates which side had
> >    some control.  Values near zero meant that you were near
> >    no-mans-land.  (Or a "front" if you will).  Large values meant that
> >    there is a strong control in that area.
> >
> >Found at: <http://www.gameai.com/influ.thread.html>
> >
> >I'm not sure if these 2 modules will be enough to work up an AI for
> >civil.  I may work up some flocking code (useful for keeping formation),
> >a finite state automata class, or some other new modules before hooking
> >them up for civil.=20
>=20
> I've read something about influence maps from Amit's AI pages, and the
> idea seems straightforward and logical to me. I'm not sure how to actually
> use a generated map for decision making, but I think that once you know
> how to use them they are very useful. One good thing about Civil is that
> units do not move too fast around the map, and the "fronts" will most
> likely be kept somewhat clean.

To be honest I'm not exactly sure how I'll use it either. But I'm new to
this and it sounds useful. I'm sure some ideas will come to me as I work
on the higher level AI components.

> >I'm hoping to eventually take these modules and create a useful AI
> >toolkit for other pygame developers. Though at my current rate that will
> >take years... I need to set aside a block of time to work on this stuff.
>=20
> Please add them to CVS. I'm interested in learning about AI. It doesn't
> matter that it's possibly something that can't actually be used yet.

Will do. The A* I have current is set up to support 5 different map
layouts. Based on all the different layouts Amit talks about. I'll
commit them all so you can check them out.

--=20

John Eikenberry
[ja...@zh... - http://zhar.net]
______________________________________________________________
"They who can give up essential liberty to purchase a little temporary
 safety, deserve neither liberty nor safety."
                                          --B. Franklin

On Mon, 11 Feb 2002, John Eikenberry wrote:

>Jan Ekholm wrote:

>In my experience there is always a tendency to overload existing classes
>(the one more method syndrom). So whenever the question comes up of
>splitting code into multiple classes, the answer is almost always yes.
>Or to put it more briefly... sounds like a good idea.

That's what I think too. I prefer having many small logical classes than a
few large mammoths.
 
>> So, where should the plans be executed then?
>> 
>> I think a good solution is to have some kind of "executor" classes under
>> engine/. These take care of executing given plans for a given turn.
>> Ideally we could have one executor for each plan, and these would contain
>> the logic that currently is in the protocol/plan/ classes, and thus
>> function like wrappers. So, for a Move class we could have a MoveExec that
>> takes care of the execution. Yes, we get more classes, but I think it's
>> better to try to keep the data for a plan separate from the logic.
>
>Sounds reasonable. Though I sort of like the idea of having all plan
>related code in one place (maybe plan/events and plan/executor). But I
>can see the sense of having all the engine code in together. [shrug]

The current idea would use:

        plan/
           for all the plans the the GUI see and use.

        engine/executor/
           for the code that executes a plan. Each plan 'Foo' in plan/
           would have one corresponding 'FooExec' in this module.

>> When the engine is done executing plans for a turns many units will
>> probably have plans that did not get executed at all, or that got
>> partially executed. The executors would then update the plans that they
>> are executing to reflect how far they actually got. All the non-finished
>> plans get sent back to the GUI:s along with the action, so that the
>> players would not lose any already given plans.
>
>How will the sever let the client know about partial executed plans?
>Will that info be in the returned action?

I think that's automatical. For moves, rotates, combat etc the plans
contain just the target or destination, no data about the current location
or state. So a 'Move' plan just says 'move from where you are now to x,y'.
Same with combat, rotations etc.

If a plan contains something that needs to be updated the engine will set
the data in the plan class, and thus it gets sent to the clients. Plans do
serialize all their members when sent over the network connection. The
engine will send back all plans that did not get fully completed, or were
not even started.

When the client has finished a turn and waits for action from the engine,
it also clears all the plans for all units. When the action data gets sent
from the engine, it also sends all remaining plans for the units.

-- 
           "Right, you bastards, you're... you're geography"
                                         -- Terry Pratchett, Guards! Guards!