ACK bug - creatures walking over obstacles

Chris H.'s Ultima / ACS-style game development system!

Moderators: Ice Cream Jonsey, Chris H

Post Reply
rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

ACK bug - creatures walking over obstacles

Post by rld » Fri Sep 02, 2011 11:30 am

I found a small bug in the ACK engine relating to creature movement over certain squares in room-type regions. Not sure if I can figure out how to fix it or not, but there appears to be a workaround.

The basic issue is that in a room-type region, if you have a stack consisting of
top - a movable item
next - an obstacle
bottom - a space

then creatures will walk over this space, even though they shouldn't be able to (and even though the player can't) because the obstacle is the top terrain item in the stack.

Also creatures will walk over

top - moveable items
bottom - obstacle

The fix seems to be to make sure that the bottom item in the stack is an obstacle (and is not the only terrain item in the stack), so if you have

top - moveable item
next - obstacle
bottom - obstacle

or

top - moveable item
next - space creatures aren't allowed to walk on
bottom - obstacle

this will work properly.

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Re: ACK bug - creatures walking over obstacles

Post by Tdarcos » Tue Sep 06, 2011 7:05 pm

rld wrote:I found a small bug in the ACK engine. The basic issue is that in a room-type region, if you have a stack consisting of
top - a movable item
next - an obstacle
bottom - a space

then creatures will walk over this space, even though they shouldn't be able to
What language is the ACK engine programmed in? If each room's content is an array or some simple structure, it's clear it's only looking at the last - highest numerical value - populated cell of the array.

If it's Pascal or C and a room's content is a linked list it's an inexcusable bug in that they're following a chain of pointers and specifically checking the last entry on the chain, while ignoring all earlier values, even though they have to traverse the entire chain to get to the bottom entry.

Joel Spolsky mentions how some people get pointers and a lot of people don't. I used them in Pascal and mainframe assembly for years before one day it clicked and I really understood them. It was at that point that I "got" pointers.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Re: ACK bug - creatures walking over obstacles

Post by rld » Thu Sep 08, 2011 1:42 pm

Tdarcos wrote:
rld wrote:I found a small bug in the ACK engine. The basic issue is that in a room-type region, if you have a stack consisting of
top - a movable item
next - an obstacle
bottom - a space

then creatures will walk over this space, even though they shouldn't be able to
What language is the ACK engine programmed in? If each room's content is an array or some simple structure, it's clear it's only looking at the last - highest numerical value - populated cell of the array.

If it's Pascal or C and a room's content is a linked list it's an inexcusable bug in that they're following a chain of pointers and specifically checking the last entry on the chain, while ignoring all earlier values, even though they have to traverse the entire chain to get to the bottom entry.

Joel Spolsky mentions how some people get pointers and a lot of people don't. I used them in Pascal and mainframe assembly for years before one day it clicked and I really understood them. It was at that point that I "got" pointers.
If you are interested, feel free to take a look at the relevant portion of the source. The link to download the ACK engine source (in Turbo Pascal) is at:

http://www.80sgaming.org/ack/source.htm

The relevant function is checkdest() in the file O_PLAY3.PAS.

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Re: ACK bug - creatures walking over obstacles

Post by Tdarcos » Thu Sep 08, 2011 8:50 pm

rld wrote:
Tdarcos wrote:
rld wrote:I found a small bug in the ACK engine.
What language is the ACK engine programmed in?
The link to download the ACK engine source (in Turbo Pascal) is at:

http://www.80sgaming.org/ack/source.htm

The relevant function is checkdest() in the file O_PLAY3.PAS.
After clicking the checkboxes and the then-active download button, I'm directed to http://www.80sgaming.org/ack/acksrc.zip which is the following:

404 (Page Not Found) Error - Ever feel like you're in the wrong place?

I may have seen this thing at some point previously and downloaded it then; I'm a connosewer of Adventure program source codes. Let me check.

Yes, I already have it, if it's version 3.251.
Last edited by Tdarcos on Thu Sep 08, 2011 9:33 pm, edited 2 times in total.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Re: ACK bug - creatures walking over obstacles

Post by rld » Thu Sep 08, 2011 9:03 pm

Tdarcos wrote:After clicking the checkboxes and the then-active download button, I'm directed to http://www.80sgaming.org/ack/acksrc.zip which is the following:

404 (Page Not Found) Error - Ever feel like you're in the wrong place?

I may have seen this thing at some point previously and downloaded it then; I'm a connosewer of Adventure program source codes. Let me check.

Yes, I already have it, if it's version 3.251.
Yeah, that's the one. This is the last official ACK version that Chris has released.

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Re: ACK bug - creatures walking over obstacles

Post by Tdarcos » Thu Sep 08, 2011 9:33 pm

rld wrote:
Tdarcos wrote:Yes, I already have it, if it's version 3.251.
Yeah, that's the one. This is the last official ACK version that Chris has released.

I'm looking at this (line numbers on right inserted by me):

Code: Select all

    if (mapobj=255) or (obj^[mapobj].t>5) then           [1]
	  begin                                               [2]
	   if mapobj<>255 then mapobj&#58;=0;                     &#91;3&#93;
	   point&#58;=locnt^&#91;roomloc&#40;room,xscc,yscc&#41;&#93;.p;          &#91;4&#93;
	   donedigging&#58;=&#40;locnt^&#91;point&#93;.p=0&#41;;                  &#91;5&#93;
	   nextpoint&#58;=point;                                  &#91;6&#93;
	   while not donedigging do                           &#91;7&#93;
	    begin                                             &#91;8&#93;
		 nextpoint&#58;=locnt^&#91;nextpoint&#93;.p;                   &#91;9&#93;
		 if locnt^&#91;nextpoint&#93;.p=0 then donedigging&#58;=true;  &#91;10&#93;
		 if &#40;locnt^&#91;nextpoint&#93;.obj<>0&#41; and &#40;locnt^&#91;nextpoint&#93;.obj<>255&#41;    &#91;11&#93;       
		  then if obj^&#91;locnt^&#91;nextpoint&#93;.obj&#93;.t<6 then     &#91;12&#93;
		   begin; mapobj&#58;=locnt^&#91;nextpoint&#93;.obj;  donedigging&#58;=true; end;  &#91;13&#93; 
		                     &#91;14&#93;
		end;                 &#91;15&#93;
	  end;                  &#91;16&#93;
I'm thinking of line 9

Code: Select all

		 nextpoint&#58;=locnt^&#91;nextpoint&#93;.p;
What I think is that this is a premature advancement of the pointer, causing it to miss the first entry and probably should go on line 14. That's my best guess from reading this code if I understand what it is doing.

This would clearly fit why the first blockage is ignored but later ones are not. And I am guessing, but I strongly suspect it does only affect the first entry, if you had one with a stack of block, block, no block it would block, it's not that it counts the last one as it ignores the first.

I'll tell you one bad thing about this code is the excessive use of manifest constants, otherwise known as "magic numbers." Someone once said the only manifest constants one should ever use in a program are 0 and 1 and possibly -1. Every other value should be a named constant. This 255 for example, what does it mean? I know from reading both this and the include file referenced elsewhere it means an object. Then a CONST like
Solid_object = 255; should be inserted, then replace all uses of 255 in these routines with Solid_object. Same for other magic numbers like the 5 on line [1] and the 6 on line [12] in this code.
Last edited by Tdarcos on Fri Sep 09, 2011 7:55 am, edited 2 times in total.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

User avatar
Ice Cream Jonsey
Posts: 21959
Joined: Sat Apr 27, 2002 2:44 pm
Location: Colorado
Contact:

Post by Ice Cream Jonsey » Thu Sep 08, 2011 9:35 pm

I gotta agree with the Commander here. That's probably it, isn't it?
the dark and gritty...Ice Cream Jonsey!

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Post by Tdarcos » Fri Sep 09, 2011 7:45 am

I've reread some comments from the guy's download page, apparently the original implementation was 20 years ago using Turbo Pascal for DOS. As such for someone who wasn't a professional I see the code is actually fairly neat (as in clean and organized). I've got "yeast in beer" complaints about how I would have organized the code such as always putting a BEGIN line by itself and its corresponding END as well as using 4 for indents instead of 1. Nothing major and mostly a difference of opinion.

What is being used to compile it, Free Pascal or Delphi and which version?

When I need to do something fast and dirty, I still have a copy of Turbo Pascal 3, probably one of the best 16-bit application tools ever devised. Hand-crafted in assembler, it fits a text editor, compiler and run-time library in a 45 K application and can create programs that, while the program and overlays, if any, need to fit in one segment (64 K), it can access the whole 640 K available to a DOS application. And it still works, even under XP.

I am asking if it uses Free Pascal or Delphi because I am presuming ATK is not still being compiled using Turbo Pascal for DOS.

Which I have a story. When I was first deciding to move to Windows I had a choice, Windows 3.1 or OS/2, which included Windows. So I bought OS/2. Turbo Pascal 6 for DOS runs perfectly fine under OS/2 as a DOS application.

Flash forward a few years and I have Windows 95. Turbo Pascal 6 for DOS crashes and will not start under Windows 95. (Of course, by then Turbo Pascal For Windows was out and so was Delphi for 32-bit Windows.)

It's a damn shame, OS/2 was probably much more stable as a 32-bit operating system than anything prior to Windows XP. Not necessarily Microsoft's fault, they had to support legacy applications and their API going back to Windows 95. OS/2 started tabula rasa.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Post by rld » Fri Sep 09, 2011 10:18 am

Tdarcos wrote: What is being used to compile it, Free Pascal or Delphi and which version?
The download package for the source comes with its own compilation environment (the Turbo Pascal compiler executables and libraries). So all you have to do is unzip it, navigate down into the directory with DosBox, and run the make file to rebuild the module you are interested in.

I have only done the "make player" rebuild up to this point to rebuild the game-playing module (ACK02). I haven't been able to get the "make all" to work; it chokes on one of the editor modules (I think the macro editor) with a "too large for code segment" error. But I haven't really wanted to mess much with the editor portion anyway, as I wanted to keep the data files compatible between the official version and my 'patched' version.

I definitely agree with you about the magic numbers. There are a lot of undocumented constants in this code...

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Post by rld » Fri Sep 09, 2011 10:40 am

I tried the suggested fix above from Tdarcos; it fixed one of the cases but not the other. Then, I decided to just take a crack at rewriting the whole loop:

Code: Select all

    if &#40;mapobj=255&#41; or &#40;obj^&#91;mapobj&#93;.t>5&#41; then
	  begin
	   if mapobj<>255 then mapobj&#58;=0;
	   nextpoint&#58;=locnt^&#91;roomloc&#40;room,xscc,yscc&#41;&#93;.p;
	   donedigging&#58;=&#40;nextpoint=0&#41;;
         point&#58;=nextpoint;		   

	   while not donedigging do
	    begin
     		 nextpoint&#58;=locnt^&#91;point&#93;.p;
		 if nextpoint=0 then donedigging&#58;=true;
		 if &#40;locnt^&#91;point&#93;.obj<>0&#41; and &#40;locnt^&#91;point&#93;.obj<>255&#41;
		  then if obj^&#91;locnt^&#91;point&#93;.obj&#93;.t<6 then
		   begin; mapobj&#58;=locnt^&#91;point&#93;.obj; donedigging&#58;=true; end;
    		point&#58;=nextpoint;		   
		end;
	  end;

This seems like it might be working correctly. I will keep an eye out for creatures stepping where they shouldn't, and if it looks ok, I will add it to a future patch.

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Post by Tdarcos » Fri Sep 09, 2011 2:01 pm

I am surprised at these:

Code: Select all

	   nextpoint&#58;=locnt^&#91;roomloc&#40;room,xscc,yscc&#41;&#93;.p;
	   donedigging&#58;=&#40;nextpoint=0&#41;;
AND
     		 nextpoint&#58;=locnt^&#91;point&#93;.p;
		 if nextpoint=0 then donedigging&#58;=true;
Today the compiler would stop you because nextpoint=0 is an illegal comparison. If point and nextpoint are pointers, 0 is an illegal comparitor, it's only supposed to allow comparison to another pointer or the constant nil which in this environment is the same as 0 but might not be on other systems. Pascal is supposed to enforce good habits like comparisons being apple <-> apple.

Also the second line in both cases is equivalent, you can change the last line if statement in this example to
donedigging:= (nextpoint=nil) ;
or
donedigging := (nextpoint=0);
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

User avatar
pinback
Posts: 13409
Joined: Sat Apr 27, 2002 3:00 pm
Contact:

Post by pinback » Fri Sep 09, 2011 3:17 pm

Totally off the subject:
Tdarcos wrote:I've got "yeast in beer" complaints
What is a "yeast in beer" complaint?

Thanks. I'll hang up and listen off the air.
Above all else... We shall go on... And continue!

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Post by Tdarcos » Fri Sep 09, 2011 6:27 pm

pinback wrote:Totally off the subject:
Tdarcos wrote:I've got "yeast in beer" complaints
What is a "yeast in beer" complaint?

Thanks. I'll hang up and listen off the air.
A "yeast in beer" comment is one in which the issue isn't critical, it's a matter of opinion. Some people don't care about finding pieces of yeast floating in their beer, some do not like it, and some do like it.

So, for example, the guy codes like this:

Code: Select all

    dosomething;
    if this=that then 
     begin dosomethingelse; movesomething&#40;here,there&#41;; end;
    for i &#58;= 1 to 5 do
     begin 
          ...
     end; 
     ...
Whereas I'd probably do it like this:

Code: Select all

    dosomething;
    if this=that then 
       begin
          dosomethingelse; 
          movesomething&#40;here,there&#41;; 
       end;
    for i &#58;= 1 to 5 do
       begin 
          ...
       end; 
    ...

Mostly minor formatting differences, I prefer to put begin/end blocks on separate lines from code. I prefer an indentation of 4 over his of 1. A disagreement of opinion and basically, if the practice is consistent, it's not critical.

I find it's easier to read code the way I do it and it makes modules less complex because you have one action per line. There are exceptions where I'd have multiple instructions on the same line, like if I'm building an array of entries, I might do something like this:

Code: Select all

    I &#58;= 1;
    item&#91;i&#93; &#58;= "Base"; I&#58;=i+1;
    item&#91;i&#93; &#58;= "Displacement"; I&#58;= I+1;
    item&#91;I&#93; &#58;= "Register"; 
    itemcount &#58;= I;
If I was initializing two arrays that are related then I might initiialize both on the same line.

This way I don't use constants and if I need to insert an item I don't have to renumber everything below it.

There are times where arrays make sense and where linked lists with pointers do. I've read various sources to Pascal compilers (which usually are themselves written in Pascal), and what I've found is they often do both. The list of reserved words is small and can be initialized at run time, this is often stored in an array.

The user's program data such as identifiers, since they don't know how big the program will be, identifiers are typically stored in a linked list. Now, the list should be alphabetized so that if a new identifier is defined, it's inserted in the list immediately after the item alphabetically higher than it. You also might have scope lists, because if you define I in a procedure it overrides I in the main program. Same for variables defined in the header of a procedure.

Whether you use arrays vs. linked lists is a matter of choice and what you have available in your language. Now, if you have a small number of items and you may want to access an item in the middle, or you're doing searches, an array might be bettter than a linked list since linked lists generally are not subject to random searches, you can go down the list or up the list but you can't go in the middle.

Now I suspect you could simulate arrays in a linked list but it would be difficult; but if you can have variant arrays where the array can be resized at will then you may have some capacity there.

If you're having to sort, say, 100 million items by reading them into memory instead of disk sorting, pointers may not get you as good a result as arrays if you can create array structures on the fly.

With being able to have gigabytes of memory on a machine it opens up new options for faster processing. (This machine I'm using has 3 GB.) Machines running 64-bit operating systems can support 8GB of memory.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

User avatar
pinback
Posts: 13409
Joined: Sat Apr 27, 2002 3:00 pm
Contact:

Post by pinback » Fri Sep 09, 2011 9:33 pm

Did you make up the term "yeast in beer complaint"? I think is it a good one! I just had never heard it before, and google returns zero results.
Above all else... We shall go on... And continue!

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Post by Tdarcos » Sun Sep 11, 2011 2:47 am

pinback wrote:Did you make up the term "yeast in beer complaint"? I think is it a good one! I just had never heard it before, and google returns zero results.
It's quite possible I may have invented the term, but for some reason I thought it was something I'd heard somewhere else.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Post by rld » Mon Sep 12, 2011 8:03 am

Tdarcos wrote:I am surprised at these:

Code: Select all

	   nextpoint&#58;=locnt^&#91;roomloc&#40;room,xscc,yscc&#41;&#93;.p;
	   donedigging&#58;=&#40;nextpoint=0&#41;;
AND
     		 nextpoint&#58;=locnt^&#91;point&#93;.p;
		 if nextpoint=0 then donedigging&#58;=true;
Today the compiler would stop you because nextpoint=0 is an illegal comparison. If point and nextpoint are pointers, 0 is an illegal comparitor, it's only supposed to allow comparison to another pointer or the constant nil which in this environment is the same as 0 but might not be on other systems. Pascal is supposed to enforce good habits like comparisons being apple <-> apple.
point and nextpoint aren't actually memory pointers in the strict sense; they are array indices. The 'linked list' used by the code is implemented inside of a predefined array, not in heap space.

User avatar
Tdarcos
Posts: 5609
Joined: Fri May 16, 2008 9:25 am
Location: Arlington, Virginia
Contact:

Post by Tdarcos » Mon Sep 12, 2011 11:39 am

rld wrote:point and nextpoint aren't actually memory pointers in the strict sense; they are array indices. The 'linked list' used by the code is implemented inside of a predefined array, not in heap space.
Well, there's part of your problem there, because confusing arrays and pointers is an excellent source of error. As I said earlier, some people get pointers and most don't, and probably the guy who wrote it wasn't good at them, which is why he's using an array to simulate a linked list. I find it interesting that usually people don't do this unless they're in a language that doesn't support pointers, like Basic or FORTRAN.
"I know what you're doing, I see it all too clear."
- Duncan Sheik, Barely Breathing

rld
Posts: 223
Joined: Sun Jan 25, 2009 2:17 am
Location: Dallas, TX

Post by rld » Mon Sep 12, 2011 1:17 pm

Tdarcos wrote:
rld wrote:point and nextpoint aren't actually memory pointers in the strict sense; they are array indices. The 'linked list' used by the code is implemented inside of a predefined array, not in heap space.
Well, there's part of your problem there, because confusing arrays and pointers is an excellent source of error. As I said earlier, some people get pointers and most don't, and probably the guy who wrote it wasn't good at them, which is why he's using an array to simulate a linked list. I find it interesting that usually people don't do this unless they're in a language that doesn't support pointers, like Basic or FORTRAN.
There are a fair amount of pointers used in the ACK source; most of the larger data arrays and structures are allocated dynamically. I think part of the reason that this was implemented as a 'pseudo-linked-list' in an array may have been to make it easier to save and restore the entire thing to disk. If you have an actual linked list with nodes in heap space, you have to traverse every single node and write them out individually, and then reconstruct the list when you read the file back in. The way that it was done here, the entire array can be blasted out and read back in with a single step.

Of course, there are many things about the ACK source and design that are non-ideal, and it shows all the hallmarks of software that has been gradually enlarged and had new bits bolted onto it over a period of many years. If it was rewritten from the ground up, cleanly, many things would be done differently, beginning with using a more modern language.

But for anyone to be motivated to work on the engine to that extent, there would probably have to be a lot more interest shown than anyone is showing right now. Other than Chris himself, no one else has yet posted a complete, working game on the forum. Heather and Garth are closest I think, and there are various other projects/WIP in various stages of completion.

Post Reply