Major improvement to the Xconq kernel

Major improvement to the Xconq kernel

[Hans Ronne]

A new path-finding code by Peter Garrone has just been checked in. It uses
the Astar algorithm and lives in the new source file path.c.

This is a major improvement to the Xconq kernel. You will notice this in
two ways:

Improved AI performance. AI-controlled units no longer get stuck at the
edges of lakes and other obstacles.

Improved ease of manual play. Now you can click anywhere on the map, and if
it is possible for your unit to get there, it will go there. No need to
micromanage unit movement any longer.

Thanks Peter!

Hans

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Thu, 13 Nov 2003, Hans Ronne wrote:

> the Astar algorithm and lives in the new source file path.c.

Which you still need to add and then check-in, according to the 
CVS record. :-)  (So if anyone is checking this out right now, my 
advice would be to wait until Hans gets path.c into the 
repository.)

> This is a major improvement to the Xconq kernel. You will notice this in

Yes.

> Thanks Peter!

Yes, thanks Peter!

Re: Major improvement to the Xconq kernel

[Hans Ronne]

>On Thu, 13 Nov 2003, Hans Ronne wrote:
>
>> the Astar algorithm and lives in the new source file path.c.
>
>Which you still need to add and then check-in, according to the
>CVS record. :-)  (So if anyone is checking this out right now, my
>advice would be to wait until Hans gets path.c into the
>repository.)

Done.

Hans

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Thu, 13 Nov 2003, Hans Ronne wrote:

> A new path-finding code by Peter Garrone has just been checked in. It uses
> the Astar algorithm and lives in the new source file path.c.
> 
> This is a major improvement to the Xconq kernel. You will notice this in
> two ways:

I will update the Windows installer and the RPM packages after I 
get out of work, so that those who do not use CVS can enjoy the 
fruits of Peter's efforts.

Eric

Re: Major improvement to the Xconq kernel

[Jim Kingdon]

> A new path-finding code by Peter Garrone has just been checked in. It uses
> the Astar algorithm and lives in the new source file path.c.

Cool.

So far I found:

* One case of a suboptimal path (went around an independent town the
  wrong way, for one hex more than needed).

* One case where an infantry just sat there in one my my towns, about
  3-5 hexes short of its destination.  It was apparently using up its
  ACP on each turn.  Won't be able to do anything about this unless I
  notice it happening again (as in, I'm not even 100% sure it was
  really a bug I saw).

* One SIGSEGV.  Most interesting part of the stack trace follows.
  Because the default compilation uses -O, it is hard to quickly
  look at the variables at that point.

#5  0x080af4da in point_in_dir (x=6, y=0, dir=135856599, xp=0xbfffde44, yp=0x0)
    at world.c:1459
#6  0x08076069 in attack_blockage (side=0x8381a98, unit=0x8189dcc,
    dirp1=1108574732) at ai.c:2483
#7  0x0807144b in ai_react_to_task_result (side=0x6, unit=0x8189dcc,
    task=0x8416394, rslt=TASK_FAILED) at ai.c:553

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Thu, 13 Nov 2003, Jim Kingdon wrote:

> > A new path-finding code by Peter Garrone has just been checked in. It uses

> * One case where an infantry just sat there in one my my towns, about
>   3-5 hexes short of its destination.  It was apparently using up its
>   ACP on each turn.  Won't be able to do anything about this unless I
>   notice it happening again (as in, I'm not even 100% sure it was
>   really a bug I saw).

I've seen this happen too (with the new path code). If you look at 
the unit's info display, does it list the movement task with a "x 
0" next to it for the entire turn?

> * One SIGSEGV.  Most interesting part of the stack trace follows.
>   Because the default compilation uses -O, it is hard to quickly
>   look at the variables at that point.

For the modern GNU C compilers, configure reports -O as part of 
the default CFLAGS. (I think I heard somewhere, perhaps on the 
gcc list, that -O and -g should now be able to work together 
without significant problems.)  My experience has been that if 
the two are used together, then sometimes you need to step a few 
lines before GDB will "backtrack" to the variable in question and 
show its assigned value; I assume that this is simply because the 
optimizer reorders instructions and it is harder to know when to 
associate a line with an instruction.

I can filter -O out of the default CFLAGS for the GNU compilers, 
if there is a consensus that this should be done. I know that 
Peter is leary about debugging optimized code.

Eric

Re: Major improvement to the Xconq kernel

[Eric McDonald]

Hi all,

On Thu, 13 Nov 2003, Eric McDonald wrote:

> I will update the Windows installer and the RPM packages after I 
> get out of work, so that those who do not use CVS can enjoy the 
> fruits of Peter's efforts.

Let's hold that thought. Looks like I spoke too soon. Some issues 
have come to light and need to be taken care of first.

  Sorry,
    Eric

Re: Major improvement to the Xconq kernel

[Peter Garrone]

On Thu, Nov 13, 2003 at 09:48:37PM -0500, Jim Kingdon wrote:
> > A new path-finding code by Peter Garrone has just been checked in. It uses
> > the Astar algorithm and lives in the new source file path.c.
> 
> Cool.
> 
> So far I found:
> 
> * One case of a suboptimal path (went around an independent town the
>   wrong way, for one hex more than needed).

I think its an optimal algorithm, provided 1 mp = 1 hex. 
I would require more information to investigate this though,
at least enough to repeat it.

> 
> * One case where an infantry just sat there in one my my towns, about
>   3-5 hexes short of its destination.  It was apparently using up its
>   ACP on each turn.  Won't be able to do anything about this unless I
>   notice it happening again (as in, I'm not even 100% sure it was
>   really a bug I saw).

Again I would need enough information to repeat this.

> 
> * One SIGSEGV.  Most interesting part of the stack trace follows.
>   Because the default compilation uses -O, it is hard to quickly
>   look at the variables at that point.
> 
> #5  0x080af4da in point_in_dir (x=6, y=0, dir=135856599, xp=0xbfffde44, yp=0x0)
>     at world.c:1459
> #6  0x08076069 in attack_blockage (side=0x8381a98, unit=0x8189dcc,
>     dirp1=1108574732) at ai.c:2483
> #7  0x0807144b in ai_react_to_task_result (side=0x6, unit=0x8189dcc,
>     task=0x8416394, rslt=TASK_FAILED) at ai.c:553

The y=0 looks highly suspicious. I did get this once myself in the coral
sea battle, but have never been able to repeat it. If anyone does get
this, could they tell us the game, and even perhaps sumit a checkpoint
file.

I have gone through
all the code I submitted and identified areas where I could be ignoring
the boundary and added extra assertion checks. I dont think
any of it is too onerous for production code.

Here is the patch.

-----------------------------------------------------------------------
diff -r -U 5 -p kernel_current/ai.c kernel/ai.c
--- kernel_current/ai.c	Fri Nov 14 18:15:41 2003
+++ kernel/ai.c	Fri Nov 14 22:13:38 2003
@@ -12,10 +12,11 @@ any later version.  See the file COPYING
    must include it. */
 
 #include "conq.h"
 #include "kpublic.h"
 #include "ai.h"
+#include <assert.h>
 
 extern void register_mplayer(AI_ops *ops);
 extern void register_iplayer(AI_ops *ops);
 
 extern int taskexecs;
@@ -2459,11 +2460,12 @@ blocked_by_enemy(Unit *unit, int tx, int
 		{
 			/* unusual situation. No previous path. Try one. */
 			dir = choose_move_direction(unit, tx, ty, 0, CMD_NONE);
 			if(dir < 0)return 0; /* blocked, but not by enemy. */
 		}
-		point_in_dir(unit->x, unit->y, dir, &x, &y);
+		if(!point_in_dir(unit->x, unit->y, dir, &x, &y))
+			return 0;
 	}
 
 
    	unit2 = unit_at(x, y);
    	if (in_play(unit2) && !trusted_side(unit->side, unit2->side))
@@ -2477,12 +2479,17 @@ blocked_by_enemy(Unit *unit, int tx, int
 int
 attack_blockage(Side *side, Unit *unit, int dirp1)
 {
     int x1,y1;
     Unit *unit2;
-	if(!dirp1)return FALSE;
-    point_in_dir(unit->x, unit->y, dirp1-1, &x1, &y1);
+    if(!dirp1)
+	return FALSE;
+    assert(dirp1 >= 1 && dirp1 <= NUMDIRS);
+    assert(in_area(unit->x,unit->y));
+    if(!point_in_dir(unit->x, unit->y, dirp1-1, &x1, &y1))
+	return FALSE;
+    assert(in_area(x1,y1));
     unit2 = unit_at(x1, y1);
     if (in_play(unit2)
         && !trusted_side(unit->side, unit2->side)
         && uu_zz_bhw(unit->type, unit2->type) > 0
         ) {
diff -r -U 5 -p kernel_current/move.c kernel/move.c
--- kernel_current/move.c	Fri Nov 14 18:15:42 2003
+++ kernel/move.c	Fri Nov 14 22:00:29 2003
@@ -6,10 +6,11 @@ it under the terms of the GNU General Pu
 the Free Software Foundation; either version 2, or (at your option)
 any later version.  See the file COPYING.  */
 
 #include "conq.h"
 #include "kernel.h"
+#include <assert.h>
 
 enum {
     over_nothing = 0,
     over_own = 1,
     over_border = 2,
@@ -223,13 +224,15 @@ do_move_action(Unit *unit, Unit *unit2, 
 	     * is only used for extraordinary circumstances, such as
 	     * retreating. In that case cached path is useless.
 	     */
 	    int dir = choose_move_direction(unit2, x, y, 0, CMD_NONE);
 	    if(dir < 0)break;
+	    assert(dir >= 0 && dir < NUMDIRS);
 
 	    /* Should be unit2 ? */
-	    interior_point_in_dir(unit->x, unit->y, dir, &ix, &iy);
+	    if(!interior_point_in_dir(unit->x, unit->y, dir, &ix, &iy))
+		break;
     	    if (type_can_occupy_cell(unit2->type, ix, iy)) {
 	    	ox = unit2->x;  
     	        oy = unit2->y;  
 		oz = unit2->z;
 	        speed = unit_speed(unit2, ix, iy);
@@ -1458,11 +1461,12 @@ pathable_point_for_unit_type(Side * side
     int fullness;
     int mpcost;
     int required_size;
     int capacity;
     if (dir >= 0) {
-	point_in_dir(tx, ty, opposite_dir(dir), &x, &y);
+	if(!point_in_dir(tx, ty, opposite_dir(dir), &x, &y))
+	    return 0;
     }
 
     /* check it the terrain itself is poisonous */
     if (terrain_always_impassable(u, t)) {
 	int c;
@@ -1657,11 +1661,12 @@ pathable_point(Unit * unit, int dir, str
 
     if (!terrain_visible(unit->side, tx, ty))
 	return 0;
 
     if (dir >= 0) {
-	point_in_dir(tx, ty, opposite_dir(dir), &x, &y);
+	if(!point_in_dir(tx, ty, opposite_dir(dir), &x, &y))
+	    return 0;
     } else {
 	x = unit->x;
 	y = unit->y;
     }
 
@@ -1796,11 +1801,13 @@ choose_move_direction(Unit * unit, int t
 	struct path_node_data *pnd;
 	int flags;
 	pnd = path_get_next_cached_node(unit, &goal_data, &flags);
 	if (pnd && flags == cmdflags) {
 	    /* assume the point is next. Do immediate call. */
-	    return path_get_next_move(unit, &goal_data, cmdflags);
+	    int dir = path_get_next_move(unit, &goal_data, cmdflags);
+	    assert(dir >= -1 && dir < NUMDIRS);
+	    return dir;
 	}
     }
 
     /* set this flag to speed things up. */
     can_be_carried = 0;
@@ -1859,10 +1866,11 @@ choose_move_direction(Unit * unit, int t
 	       unit->id,
 	       unit->type, u_type_name(unit->type),
 	       unit->x, unit->y, tx, ty, distance(unit->x, unit->y, tx,
 						  ty), path_cb_cnt, dir);
 
+    assert(dir >= -1 && dir < NUMDIRS);
     return dir;
 }
 
 /*
  * Return the transport unit if a transport change on an
@@ -1889,10 +1897,11 @@ get_cached_move_direction(Unit * unit, i
 {
     struct path_node_data goal_data;
     int dir;
     set_node_data(&goal_data, x, y, 0);
     dir = path_get_next_cached_move(unit, &goal_data);
+    assert(dir >= -1 && dir < NUMDIRS);
     return dir;
 }
 
 /*
  * Return a hash index based on node data coordinates.
@@ -1976,10 +1985,12 @@ cost_to_move_on_path(void *pkey, const s
 
     /* points should be adjacent. */
     dir = closest_dir(tx - x, ty - y);
     if (dir < 0)
 	return -1;
+
+    assert(dir < NUMDIRS);
 
     if (!pathable_point(unit, dir, p2, cmdflags, &mp_cost))
 	return -1;
 
     return mp_cost;
diff -r -U 5 -p kernel_current/task.c kernel/task.c
--- kernel_current/task.c	Fri Nov 14 18:15:43 2003
+++ kernel/task.c	Fri Nov 14 21:59:52 2003
@@ -6,10 +6,11 @@ it under the terms of the GNU General Pu
 the Free Software Foundation; either version 2, or (at your option)
 any later version.  See the file COPYING.  */
 
 #include "conq.h"
 #include "kernel.h"
+#include <assert.h>
 
 /* This is the number of tasks to allocate initially.  More will always be
    allocated as needed, so this should be a "reasonable" value. */
 
 #ifndef INITMAXTASKS
@@ -956,12 +957,14 @@ do_approach_subtask(Unit *unit, int tx, 
     if(s == 0 && !terrain_visible(unit->side, tx, ty))s++;
 
     dir = choose_move_direction(unit, tx, ty, s, cmdflags);
 
     if(dir < 0)return TASK_FAILED;
+    assert(dir >= 0 && dir < NUMDIRS);
 
-    point_in_dir(unit->x, unit->y, dir, &nx, &ny);
+    if(!point_in_dir(unit->x, unit->y, dir, &nx, &ny))
+	return TASK_FAILED;
 
     /* first, check any enemy on route. */
     for_all_stack(nx, ny, unit2) {
 	if (!trusted_side(unit->side, unit2->side)) {
             if (unit->occupant) {
@@ -1011,15 +1014,17 @@ do_approach_subtask(Unit *unit, int tx, 
 
 	if(!u_trans)
 	{
 	    /* try to hijack a ferry on any adjacent hex. */
 	    int i;
-	    for(i=0;i<6;i++)
+	    for(i=0;i<NUMDIRS;i++)
 	    {
 		int x,y;
-		if(i == dir)continue;
-                point_in_dir(unit->x, unit->y, i, &x, &y);
+		if(i == dir)
+		    continue;
+                if(!point_in_dir(unit->x, unit->y, i, &x, &y))
+		    continue;
 	        for_all_stack(x, y, unit2) {
 	            if(could_directly_board_ferry(unit,unit2))
 		    {
 		        u_trans = unit2;
 		        break;

Re: Major improvement to the Xconq kernel

[Jim Kingdon]

> The y=0 looks highly suspicious.

The y=0 is probably an artifact of having optimization on.  Note that
yp is shown as NULL, which can't be true (it is passed in as &y1), so
presumably the debugger isn't up on what is going on.

Re: Major improvement to the Xconq kernel

[Jim Kingdon]

> (I think I heard somewhere, perhaps on the gcc list, that -O and -g
> should now be able to work together without significant problems.)  My
> experience has been that if the two are used together, then sometimes
> you need to step a few lines before GDB will "backtrack" to the
> variable in question and show its assigned value; I assume that this
> is simply because the optimizer reorders instructions and it is harder
> to know when to associate a line with an instruction.

The kind of thing which you describe has always been typical of what
happens with -O and -g.  I call it a "significant problem" trying to
debug code this way, though that is partly a matter of opinion.
Stepping is not an option; I only had a core dump, not a running copy.
In general, you need to read the disassembly to figure out what is
going on, and who wants to bother?

> I can filter -O out of the default CFLAGS for the GNU compilers, 
> if there is a consensus that this should be done. I know that 
> Peter is leary about debugging optimized code.

I suspect the default is chosen with production, rather than
debugging, in mind.  Even for production, this might be misguided:
even a user which knows nothing about debugging could send in a
backtrace after a core dump.  Although there's also a case for the
status quo (don't know if anyone has tried to measure the performance
gain from -O).

Meanwhile, I can always change my own CFLAGS.

Re: Major improvement to the Xconq kernel

[Hans Ronne]

>> * One SIGSEGV.  Most interesting part of the stack trace follows.
>>   Because the default compilation uses -O, it is hard to quickly
>>   look at the variables at that point.
>>
>> #5  0x080af4da in point_in_dir (x=6, y=0, dir=135856599, xp=0xbfffde44,
>>yp=0x0)
>>     at world.c:1459
>> #6  0x08076069 in attack_blockage (side=0x8381a98, unit=0x8189dcc,
>>     dirp1=1108574732) at ai.c:2483
>> #7  0x0807144b in ai_react_to_task_result (side=0x6, unit=0x8189dcc,
>>     task=0x8416394, rslt=TASK_FAILED) at ai.c:553
>
>The y=0 looks highly suspicious.

Indeed. I've had problems with point_in_dir before at the map edge.

>I have gone through
>all the code I submitted and identified areas where I could be ignoring
>the boundary and added extra assertion checks. I dont think
>any of it is too onerous for production code.
>
>Here is the patch.

I'll check it in. I don't have much time for more testing right now, but
hopefully others could have a go at it.

Hans

Re: Standing Orders

[Alan Kenwright]

Lincoln Peters wrote:

> 1. In bolodd, there is a "tower" unit that does not move, and it can
see
> and fire at any hostile units up to 8 cells away.  It can also
> manufacture guided missiles of various kinds.

This interested me.  It reminded me in some ways of the missiles that
get built in a game of "Apocalypse" (which was originally called
"Warlord").  These board games have both  been out of production for
years (and the names re-used for other things), but were actually very
good map-based games not hugely dissimilar to Xconq.  The reason I bring
this up is firstly that the game (the two are actually the same game
just made by different companies and played on different sized maps) had
some quite unusual and interesting aspects, both in game play and
strategy, and secondly because the game had quite concise and precise
rules (which are available on the net at
http://boardgamegeek.com/viewfile.php3?fileid=3097 ).  I played quite a
number of games of Apocalypse and never found a situation where the
rules were ambiguous or unclear, which is generally a pretty good sign.
It's primarily a strategy game based on war and is therefore not overly
"realistic" (neither is chess, but that's a pretty good game too).  The
thing which made the game a bit long winded was having to count the
numbers of various kinds of territory occupied (mountains, rural areas,
urban areas, etc) to calculate the number of armies allotted, which it
strikes me would be far better done by computer.

Unfortunately my programming skills are pretty well none-existent, so
it's not something I could undertake and I'm not asking anyone to do it
for me.  I just offer it up because if you've never seen the game you
might find it entertaining (it's pretty easy to make a version, all you
need is a map, lots of  small counters, something to represent nuclear
missiles and a dice - which is used in the most bizarre way, but I won't
spoil it for you), and because the people designing new games might find
some inspiration in some of the strategy elements.

I've enjoyed playing Xconq over a number of years and am truly grateful
for all the hard work the developers have put in.  The improvements over
the last 12 months have been great.  My only reservation is that a fair
number, though by no means all(!), of the games modules are just
re-workings of the standard game (substituting chariots or spaceships
for tanks, or whatever) and it would be good to see some new elements of
play/strategy coming in.  Even if no-one wants to take me up on that, I
hope some of you have a look at Apocalypse and let me know what you
think.  (I should maybe add that I'm not a wargamer - Xconq and
Apocalypse are about as far as I go in that direction with maybe an odd
game of Risk if the situation demands it).  If anybody is interested in
Apocalypse and can't manage to find/make a map, please get in touch and
I'll see if I can find one.

Cheers
--
Alan.

Alan M Kenwright                        Phone +44-191-334-2095
Senior Research Officer (NMR)
Department of Chemistry
University of Durham
Durham  DH1 3LE       UK

Re: Standing Orders

[Hans Ronne]

>I've enjoyed playing Xconq over a number of years and am truly grateful
>for all the hard work the developers have put in.  The improvements over
>the last 12 months have been great.  My only reservation is that a fair
>number, though by no means all(!), of the games modules are just
>re-workings of the standard game (substituting chariots or spaceships
>for tanks, or whatever) and it would be good to see some new elements of
>play/strategy coming in.

Thank you for your kind words. As for something very different from the
standard Xconq game, you may want to check out the Specula game by Elijah
Meeks. It is available at:

http://castironlife.sourceforge.net/spec.zip

I will add it to the distribution when I am done updating the game library.

Hans

Re: Standing Orders

[Jim Kingdon]

> "Apocalypse" (which was originally called "Warlord")
> http://boardgamegeek.com/viewfile.php3?fileid=3097

Hmm.

xconq isn't really a framework which is general enough to implement a
game like that.  There are plenty of details (non-hexagonal map, more
complicated combat rules than just "attack and randomly win or lose",
etc, etc), but the most fundamental is whether you hope to have a
general AI still able to figure out how to play the game.  Even with
xconq's existing level of generality, it can still be an issue for the
AI, because it can't just have things hardcoded like what units to
build.

It does sound like an interesting game, though.

Re: Standing Orders

[Hans Ronne]

>xconq isn't really a framework which is general enough to implement a
>game like that.  There are plenty of details (non-hexagonal map ...

Non-hexagonal maps would be easy to implement if we had a more useful
country/province concept. One would just set movement costs within the
province to zero, and get a Risk-type game. Right now, you can define
provinces as features, but they just serve as decorations. They don't mean
anything to the kernel.

Hans

-O -g

[Brandon J. Van Every]

Jim Kingdon wrote:
>
> The kind of thing which you describe has always been typical of what
> happens with -O and -g.

Why bother with -O?  Can't speak for other platforms, but compiling
under Windows using VS 2003, I don't observe any slowdown running a
debug only version of the Tk client.  This is on a 866 MHz Pentium III.
I think this indicates that Tk is a super-pig super-bottleneck.


Cheers,                     www.indiegamedesign.com
Brandon Van Every           Seattle, WA

Taking risk where others will not.

Re: -O -g

[Stan Shebs]

Brandon J. Van Every wrote:

>Jim Kingdon wrote:
>
>>The kind of thing which you describe has always been typical of what
>>happens with -O and -g.
>>
>
>Why bother with -O?  Can't speak for other platforms, but compiling
>under Windows using VS 2003, I don't observe any slowdown running a
>debug only version of the Tk client.  This is on a 866 MHz Pentium III.
>I think this indicates that Tk is a super-pig super-bottleneck.
>
Pig perhaps, but bottleneck no. Xconq's critical paths don't involve
tcl's own code; that was a key criterion for adopting tcl. Check out
the map drawing code in any of the GUIs to see where the real
optimization struggle is going on.

Stan

Re: Standing Orders

[Eric McDonald]

On Fri, 14 Nov 2003, Hans Ronne wrote:

> >xconq isn't really a framework which is general enough to implement a
> >game like that.  There are plenty of details (non-hexagonal map ...
> 
> Non-hexagonal maps would be easy to implement if we had a more useful
> country/province concept. One would just set movement costs within the
> province to zero, and get a Risk-type game. Right now, you can define

Good thinking. We should make sure that idea is in doc/PROJECTS.

Eric

Re: -O -g

[Hans Ronne]

>Pig perhaps, but bottleneck no. Xconq's critical paths don't involve
>tcl's own code; that was a key criterion for adopting tcl. Check out
>the map drawing code in any of the GUIs to see where the real
>optimization struggle is going on.

I wouldn't call it an optimization struggle as much as a human perception
struggle. It is possible to increase the speed of the game10-fold by simply
reducing the animation time, but then you can no longer grasp what is going
on. See the profiling data I posted last year:

http://sources.redhat.com/ml/xconq7/2002/msg00574.html

Hans

Animation time (was: Re: -O -g)

[Lincoln Peters]

On Fri, 2003-11-14 at 12:34, Hans Ronne wrote:
> I wouldn't call it an optimization struggle as much as a human perception
> struggle. It is possible to increase the speed of the game10-fold by simply
> reducing the animation time, but then you can no longer grasp what is going
> on. See the profiling data I posted last year:

Might it be possible to set up Xconq in such a way that animations can
run while other things are running?  Perhaps when an explosion appears
on the screen, Xconq would draw it, proceed to other things, but then
erase it after the animation time has elapsed?

If a lot of combat occurs in a short amount of time (most likely for
units under AI control or directed by standing orders), the screen might
get messy with all of the explosions appearing simultaneously, but so
would a real battlefield.

Re: Animation time (was: Re: -O -g)

[Hans Ronne]

>On Fri, 2003-11-14 at 12:34, Hans Ronne wrote:
>> I wouldn't call it an optimization struggle as much as a human perception
>> struggle. It is possible to increase the speed of the game10-fold by simply
>> reducing the animation time, but then you can no longer grasp what is going
>> on. See the profiling data I posted last year:
>
>Might it be possible to set up Xconq in such a way that animations can
>run while other things are running?  Perhaps when an explosion appears
>on the screen, Xconq would draw it, proceed to other things, but then
>erase it after the animation time has elapsed?

This was also discussed in the same thread last year. See:

http://sources.redhat.com/ml/xconq7/2002/msg00578.html

Cutting down animation times does make the game very confusing (I have
tested). Re-reading my post I see that I had some ideas, like highlighting
the attacking unit, which could make it possible to cut the animation times
with less confusion. And the animation pre-flight code from the Mac
interface could probably be ported to the tcltk interface.

As for the multi-threaded (or delayed erasure) approach, a problem is that
the kernel moves one unit at a time. This is true even if the game is
running in non-sequential mode. So weird things could happen if a unit is
hit several times, perhaps by different attackers, and therefore would have
several animations running on top of each other.

>If a lot of combat occurs in a short amount of time (most likely for
>units under AI control or directed by standing orders), the screen might
>get messy with all of the explosions appearing simultaneously, but so
>would a real battlefield.

Exactly. I think the best (or at least less confusing) way would be to
maintain a linear sequence of events, but make the animations easier to
interpret for the human brain. They could then probably be played faster
than now.

Hans

RE: Animation time

[Brandon J. Van Every]

Hans Ronne wrote:
>
> Exactly. I think the best (or at least less confusing) way would be to
> maintain a linear sequence of events, but make the animations
> easier to
> interpret for the human brain. They could then probably be
> played faster than now.

Ok, having played a few zillion hours of Civ and SMAC, I can safely say
the following about the 4X TBS genre:

1) all games of this genre suffer from unit scaleup problems as the game
progresses.

2) once you're dealing with hordes, watching all the battles is
interminably dull.

The assumption that everything must be watched is fundamentally
incorrect.  It may very well be intelligible; it is also as much fun as
watching grass grow.  I suggest that The Solution is rapid simultaneous
movement display, with a local Replay feature if the player wants to see
how a specific battle actually went.  If you blasted your enemy to
smithereens, and you're marching onwards just as you'd expect, what do
you care about how it happened?  You *know* that your tank horde is
going to crush that stack of obsolete, puny spearmen.

I'm not sure how much work a local Replay feature would be.  I'm sure
it's not a trivial amount of work, since you need to record all the game
states.

A more advanced idea might be a Passive Replay system.  The player does
not need to say that he wants a replay; rather, ghosts of how the battle
went are played in in a continuous but slow loop.  As the player scrolls
around and stops to look somewhere, to contemplate his next move, he
sees the ghosts of what happened before.  This could be modal: if the
player finds it distracting, he could turn it off.


Cheers,                     www.indiegamedesign.com
Brandon Van Every           Seattle, WA

Taking risk where others will not.

Re: Standing Orders

[Eric McDonald]

Hi Alan, Lincoln, others,

On Fri, 14 Nov 2003, Alan Kenwright wrote:

> Lincoln Peters wrote:
> 
> > 1. In bolodd, there is a "tower" unit that does not move, and it can
> see
> > and fire at any hostile units up to 8 cells away.  It can also
> > manufacture guided missiles of various kinds.

It is good that you mentioned that they are guided. Something that 
Xconq does not currently have is the concept of the different 
varieties of missile weapons: projectile (launched along a simple 
path, unguided), guided (player guided, arbitrary target), and 
seeker (computer guided, locked target).

Empire Master (which Chris Eliot is no longer developing; he is 
now a CS professor) did make the distinction between guided and 
unguided missiles, and I found it to be quite useful. For 
example, one could define spy satellites to be projectiles with no 
range restricitions.

> strategy, and secondly because the game had quite concise and precise
> rules (which are available on the net at
> http://boardgamegeek.com/viewfile.php3?fileid=3097 ).  

Very interesting....

> Unfortunately my programming skills are pretty well none-existent, so
> it's not something I could undertake and I'm not asking anyone to do it
> for me.  I just offer it up because if you've never seen the game you

Thanks for suggesting it.

> missiles and a dice - which is used in the most bizarre way, but I won't
> spoil it for you)

Quite novel. :-)

> re-workings of the standard game (substituting chariots or spaceships
> for tanks, or whatever) and it would be good to see some new elements of
> play/strategy coming in.  

One idea I have been toying with for awhile is a hex-based 
Stratego-like game. I think I have figured out ways that most of 
it could be implemented with Xconq.... Would this interest anyone?

> Alan.

Alan, I seem to remember you emailing me a couple of months ago, 
and you mentioned that you were successfully running Xconq on XP. 
Have you had a chance to try the installer yet, and, if so, did 
that work for you?

  Regards,
   Eric

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Thu, 13 Nov 2003, Eric McDonald wrote:

> On Thu, 13 Nov 2003, Eric McDonald wrote:
> 
> > I will update the Windows installer and the RPM packages after I 
> > get out of work, so that those who do not use CVS can enjoy the 
> > fruits of Peter's efforts.
> 
> Let's hold that thought. Looks like I spoke too soon. Some issues 
> have come to light and need to be taken care of first.

There is still at least one known issue with the path-related 
code, though the crashing bugs now seem to be squashed. There are 
also several other rather critical things that I would like to 
address before releasing a new Windows installer and RPM's. If 
all goes well, I hope to release sometime tomorrow (GMT -0700).

Eric

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Thu, 13 Nov 2003, Jim Kingdon wrote:

> So far I found:

> * One case where an infantry just sat there in one my my towns, about
>   3-5 hexes short of its destination.  It was apparently using up its
>   ACP on each turn.  Won't be able to do anything about this unless I
>   notice it happening again (as in, I'm not even 100% sure it was
>   really a bug I saw).

I just checked a patch into CVS that might have addressed this 
problem (which Hans and I were also seeing in one form or 
another). If anyone (in addition to me) can test whether the patch 
addresses the problem or not, I would be grateful. It seemed to 
have helped in the cases that I was seeing.

Eric

Re: Major improvement to the Xconq kernel

[Hans Ronne]

>On Thu, 13 Nov 2003, Jim Kingdon wrote:
>
>> So far I found:
>
>> * One case where an infantry just sat there in one my my towns, about
>>   3-5 hexes short of its destination.  It was apparently using up its
>>   ACP on each turn.  Won't be able to do anything about this unless I
>>   notice it happening again (as in, I'm not even 100% sure it was
>>   really a bug I saw).
>
>I just checked a patch into CVS that might have addressed this
>problem (which Hans and I were also seeing in one form or
>another). If anyone (in addition to me) can test whether the patch
>addresses the problem or not, I would be grateful. It seemed to
>have helped in the cases that I was seeing.

It seems to fix the problem, at least in the intro game. No more units in
Exploratory Reserve. I have a feeling that exploration is still a little
slower than previously, but that may just be a consequence of the AI being
better at completing previously assigned move-to tasks before it does
something else.

Hans

Re: Major improvement to the Xconq kernel

[Peter Garrone]

On Sat, Nov 15, 2003 at 12:10:33AM -0500, Eric McDonald wrote:
> On Thu, 13 Nov 2003, Eric McDonald wrote:
> 
> > On Thu, 13 Nov 2003, Eric McDonald wrote:
> > 
> > > I will update the Windows installer and the RPM packages after I 
> > > get out of work, so that those who do not use CVS can enjoy the 
> > > fruits of Peter's efforts.
> > 
> > Let's hold that thought. Looks like I spoke too soon. Some issues 
> > have come to light and need to be taken care of first.
> 
> There is still at least one known issue with the path-related 
> code, though the crashing bugs now seem to be squashed. There are 
> also several other rather critical things that I would like to 
> address before releasing a new Windows installer and RPM's. If 
> all goes well, I hope to release sometime tomorrow (GMT -0700).
> 
> Eric

Maybe we should delay just a little bit more, get the testing cirle a
bit wider, to avoid unnecessary rebuilds. We might be getting a little
over-keen perhaps. I dont really know how the building setup works on
this game. I think I probably suppressed my own observations of a
few of these reported problems. Its easy to do.
 Cheers,
  Peter

Re: Major improvement to the Xconq kernel

[Eric McDonald]

On Sun, 16 Nov 2003, Peter Garrone wrote:

> Maybe we should delay just a little bit more, get the testing cirle a
> bit wider, to avoid unnecessary rebuilds. 

Sure. I think I am going to delay at least another day. I do think 
all of the known major issues have been addressed. There might be 
a few minor things:

(1) Now that paths can be computed through unexplored hexes, the 
question is what should the cost of an unexplored hex be? If the 
cost is low like it is now, then paths through them will be 
favored over known paths. This doesn't matter if a unit is 
exploring the unknown, but if it is trying to get from known point 
A to known point B, then we either need to favor the partially 
unexplored path, or else avoid it. I'm not entirely sure which....
(2) We need to make sure that a unit moving along a cached path 
does not move into vanishes-on or wrecks-on terrain, if that 
terrain was not visible when the path was first computed. We 
should do so without peeking at the terrain during path 
computation, otherwise it opens the door to cheating.... This 
probably implies that a check is needed before each move along the 
cached path, if a check does not already exist (I haven't looked 
yet).
(3) We need to make sure that a unit moving along a 
cached path will stop following that path if it is low on 
supplies. I have seen several instances of units getting stranded 
(due to low supplies) when they pulled out of supply range while 
heading to a remote destination. (This might not be strictly a 
path-related problem.)

> over-keen perhaps. I dont really know how the building setup works on
> this game.

Both the RPM and Windows installer builds are fairly trivial and 
don't consume much time. The only problem I have with releasing 
several times in a couple of days is that I have to boot into 
Windows to make the installer program.

> I think I probably suppressed my own observations of a
> few of these reported problems. Its easy to do.

Well, I think it was good to bring the code forward when you did. 
With more eyes looking at it and how it behaves, we can track and 
fix things quicker than you could by yourself.

  Regards,
    Eric

favoring known or unknown paths

[Brandon J. Van Every]

Eric McDonald wrote:
>
> (1) Now that paths can be computed through unexplored hexes, the
> question is what should the cost of an unexplored hex be? If the
> cost is low like it is now, then paths through them will be
> favored over known paths. This doesn't matter if a unit is
> exploring the unknown, but if it is trying to get from known point
> A to known point B, then we either need to favor the partially
> unexplored path, or else avoid it. I'm not entirely sure which....

If the unknown is favored, then players will be irritated when their
units (1) are killed by unknowns, (2) take an unreasonable amount of
time to get somewhere, because for instance they walked across an
endless mountain range, (3) can't get to the destination because a
land-water boundary blocks their way.

If the known is favored, then units aren't going to "cut across the
black" unless that would be the best option even in the worst case.
(Assuming passable terrain.)  Or if one end of the path is in the black.
Ergo, favoring the known doesn't prevent exploring the black.

So, I think the known should be favored.  Make all the unknown hexes
cost as much as a mountain.

Keep in mind that as a unit moves, a little bit of the unknown becomes
known.  It may be worth locally recomputing the path for a couple of
hexes as the unit moves.

If you wanted to get fancy, you could implement a "Terrain Guesser."
For instance if you've swam around in a big circle in the ocean, you can
probably guess that the interior is filled with more ocean.  If you're
near the north and south poles, you might guess that more terrain will
be tundra or glaciers.  If you've seen 2 piles of mountains that seem to
run in a line towards each other, it's probably a good bet that the
mountain range continues.  If there's a lot of jungle in your part of
the world, then you're probably going to be crossing more jungle.

A Terrain Guesser, of course, can only guess.


Cheers,                     www.indiegamedesign.com
Brandon Van Every           Seattle, WA

Taking risk where others will not.

Re: Major improvement to the Xconq kernel

[Peter Garrone]

On Sun, Nov 16, 2003 at 03:33:32PM -0500, Eric McDonald wrote:
> On Sun, 16 Nov 2003, Peter Garrone wrote:
> 
> > Maybe we should delay just a little bit more, get the testing cirle a
> > bit wider, to avoid unnecessary rebuilds. 
> 
> Sure. I think I am going to delay at least another day. I do think 
> all of the known major issues have been addressed. There might be 
> a few minor things:
> 
> (1) Now that paths can be computed through unexplored hexes, the 
> question is what should the cost of an unexplored hex be? If the 
> cost is low like it is now, then paths through them will be 
> favored over known paths. This doesn't matter if a unit is 
> exploring the unknown, but if it is trying to get from known point 
> A to known point B, then we either need to favor the partially 
> unexplored path, or else avoid it. I'm not entirely sure which....

I'm working on a patch so that the unexplored part is 2 MP per hex.
Therefore if a unit gets
a command to explore a distant hex, it will preferentially travel over
known teritory before entering the black. If the destination is unknown,
then an exploring flag bit is set. If that bit is not set, it will not
travel in the black.

> (2) We need to make sure that a unit moving along a cached path 
> does not move into vanishes-on or wrecks-on terrain, if that 
> terrain was not visible when the path was first computed. We 
> should do so without peeking at the terrain during path 
> computation, otherwise it opens the door to cheating.... This 
> probably implies that a check is needed before each move along the 
> cached path, if a check does not already exist (I haven't looked 
> yet).

In my proposed patch a path node that was in the unknown has a special flag bit set.
If that bit is set, then the path is recalculated each hex. That
way an exploring unit will follow roads and avoid obstacles. It
should be reasonably efficient because searching in the black is cheap.


> (3) We need to make sure that a unit moving along a 
> cached path will stop following that path if it is low on 
> supplies. I have seen several instances of units getting stranded 
> (due to low supplies) when they pulled out of supply range while 
> heading to a remote destination. (This might not be strictly a 
> path-related problem.)

I have later plans to incorporate refueling behavior into the
pathfinding algorithm. The node state would be position and amount of
fuel. As a node runs out of fuel it becomes un-pathable, so to speak.
With care, it should be possible to transport aircraft across the board,
without needing to plan all the refueling stops.

I dont think the current behavior is different to the prior behavior,
so perhaps we should get to the prior functionality first.

Peter

Re: Major improvement to the Xconq kernel

[Eric McDonald]

Hi Peter,

On Mon, 17 Nov 2003, Peter Garrone wrote:

> In my proposed patch a path node that was in the unknown has a special flag bit set.
> If that bit is set, then the path is recalculated each hex. That
> way an exploring unit will follow roads and avoid obstacles. It
> should be reasonably efficient because searching in the black is cheap.

Sounds good. I think that addresses the issue.

> > (due to low supplies) when they pulled out of supply range while 
> > heading to a remote destination. (This might not be strictly a 
> > path-related problem.)
> 
> I have later plans to incorporate refueling behavior into the
> pathfinding algorithm. The node state would be position and amount of
> fuel. As a node runs out of fuel it becomes un-pathable, so to speak.
> With care, it should be possible to transport aircraft across the board,
> without needing to plan all the refueling stops.

Good.

> I dont think the current behavior is different to the prior behavior,
> so perhaps we should get to the prior functionality first.

Might not be. And, like I said, I am not sure it is path-related. 
Along as the SupplyLow flags are checked as a unit is advancing 
along a cached path, then I think we basically have the old 
behavior. (Namely, automatic movement would cease when a supply 
became low.)

There seem to be some other factors at work wrt the supply 
problem.

  Regards,
   Eric

Re: Major improvement to the Xconq kernel

[Peter Garrone]

----- Forwarded message from Peter Garrone <pgarrone@acay.com.au> -----

From: Peter Garrone <pgarrone@acay.com.au>
To: Hans Ronne <hronne@comhem.se>
Subject: Re: Major improvement to the Xconq kernel

On Thu, Nov 13, 2003 at 10:36:24PM +0100, Hans Ronne wrote:
> A new path-finding code by Peter Garrone has just been checked in. It uses
> the Astar algorithm and lives in the new source file path.c.
> 
> This is a major improvement to the Xconq kernel. You will notice this in
> two ways:
> 
> Improved AI performance. AI-controlled units no longer get stuck at the
> edges of lakes and other obstacles.
> 
> Improved ease of manual play. Now you can click anywhere on the map, and if
> it is possible for your unit to get there, it will go there. No need to
> micromanage unit movement any longer.
> 
> Thanks Peter!
> 
> Hans
> 
> 
Thank you Hans. I would like so say I enjoyed cooperating with Hans
and Eric on this project, and I got the basic information from
Justin Heyes-Jones web site, including the pseudo-code, though not the
code.
 Peter

----- End forwarded message -----