NPC can wander outside of settlement map

[plaidpants]

Needed to add this code to prevent the npc from wandering outside of the currently loaded map. This is especially evident in moonglow where the town doesn't have any walls and the wandering jester will wander out of town and cause an exception in the code.

C_51A7(bp0a, bp08, bp06, bp04)
int bp0a;
int bp08;
int bp06;
int bp04;/*# of tries*/
{
	unsigned bp_02, bp_04;

	bp_02 = D_8742._npc._x[bp0a];
	bp_04 = D_8742._npc._y[bp0a];

	if ((bp08 + bp_02 < 0) || (bp08 + bp_02 > 31) || (bp06 + bp_04 < 0) || (bp06 + bp_04 > 31))
	{
		printf("attempt to move npc %d outside the current map (%d,%d) move delta (%d,%d)\n", bp0a, bp_02, bp_04, bp08, bp06);
		return;
	}
	if(U4_RND1(1) && bp08) {
		if(C_4E94(bp0a, bp08+bp_02, bp_04, D_8742._map.x32x32[bp_04][bp08+bp_02])) // TODO: this NPC move has no protection if the  current NPC position is 0 and the random move is -1 when accessing the map tile
			C_4FF8(bp0a, bp08+bp_02, bp_04);
		return;
	}
	if(bp06) {
		if(C_4E94(bp0a, bp_02, bp06+bp_04, D_8742._map.x32x32[bp06+bp_04][bp_02])) // TODO: this NPC move has no protection if the  current NPC position is 0 and the random move is -1 when accessing the map tile
			C_4FF8(bp0a, bp_02, bp06+bp_04);
		return;
	}
	if(C_4E94(bp0a, bp08+bp_02, bp_04, D_8742._map.x32x32[bp_04][bp08+bp_02])) { // TODO: this NPC move has no protection if the  current NPC position is 0 and the random move is -1 when accessing the map tile
		C_4FF8(bp0a, bp08+bp_02, bp_04);
		return;
	}
	if(D_8742._npc._var[bp0a] != 0x80 && bp04 >= 0)
		C_51A7(bp0a, u4_sign((char)u_rand_a()), u4_sign((char)u_rand_a()), bp04 - 1);
}

[cambragol]

I don't recall seeing this behavior in my builds. Maybe I missed it...? In Threat of the Trinity NPCs stay within the town border, though I did modify most of the code around this both long ago and recently. I can't recall what I did precisely.
NPCs don't move outside of town in the original DOS game.

[plaidpants]

I can force the issue with the jester in moonglow by standing in front of him while he attempts to move an eventually blocking in on the left or upper edge or in the corner and he will eventually attempt to move outside the map boundary and the code will flag an exception trying to access a less than zero array index in x32x32[][].

[cambragol]

Hmph. I can't replicate this behavior in the original DOS and TotT. I have not tested a build of u4-decompiled though.

[plaidpants]

There could be other code below this function that prevents the actual move but I don't get there after the exception when it accesses the out of bound array.

[cambragol]

I thought something like that. Which might mean this exception is an artifact of your build environment?

[plaidpants]

I suspect that because there are so few of the 256 tile values that can be walked on, the npcs will not attempt to walk outside of the settlement most of the time as most of the the surrounding tiles will not be walk-able but if any memory locations stored near the x32x32 map contains any values that correspond to a walk-able tile the npc could attempt to walk outside the bounds of the map. Since the npc are stored as just positions and do not modify the map this might not be a terrible thing and may not corrupt anything but accesses to memory outside of a defined array is still something to be wary of. FYI here is another screenshot.

[cambragol]

Interesting view....

[jaredr]

Oh, fer-cryin-out-loud @plaidpants, I thought surely no one else had this idea about a nearly 40 year old game!

(sorry for the thread hijack)

[ergonomy-joe]

@plaidpants I couldn't reproduce the problem either.
moreover, function C_4E94 controls that neither the x or y will be over 32 after the attempted move (since, the x and y value are converted to unsigned values, the case where they might be negative is taken into acount too).
My guess, is that it is the access to array D_8742._map.x32x32 with out of range values (negative or above 31) which causes the exception.
As I said, I couldn't reproduce the problem with Visual Studio 2008.
You are using 2019 right ? Do you have a way to disable the exceptions locally or just for this array, so we can verify that the NPC doesn't actually leave the map ?

update: sorry, I didn't see read your post concerning the exception yet.
So basically you are right, out-of-bounds access is bad coding. But this is the original code, and this doesn't cause any issues in the original environment so I guess I will leave it this way. I may add a comment in the code though.

[plaidpants]

I tried a few things (#pragma's and such) but I don't seem to be able to disable this check in VS2019, might also be OS enforced so I am not able to see if anything downstream is impacted. Your plan for a comment sounds good.

Unhandled exception at 0x00007FF68D5887F7 in UN_U4.exe: 0xC0000005: Access violation reading location 0x00007FF78D5C231F.

[Fenyx4]

Oh, fer-cryin-out-loud @plaidpants, I thought surely no one else had this idea about a nearly 40 year old game!

(sorry for the thread hijack)

That looks cool. Putting the map on a toroid?

[ergonomy-joe]

I managed to reproduce the exception. So it seems to happen only in x64 mode, and only in the cases where (bp08 + bp_02) or (bp06 + bp_04) are negatives.
Since the sums are cast as unsigned, a -1 value becomes 0xffffffffffffffff, which leads to a very far memory access, hence the exception.
A simple workaround would be to cast or limit the sums for the array access:
D_8742._map.x32x32[bp_04][(bp08+bp_02)&0x1f]
D_8742._map.x32x32[(bp06+bp_04)&0x1f][bp_02]

I may leave the issue opened while thinking about it.

btw, I too like the toroid view. Can you upload an animated view in youtube ?

[plaidpants]

@ergonomy-joe I didn't create the toroid view, @jaredr did, but here is a youtube video of mine in action Original Ultima 4 in VR

[ergonomy-joe]

I just changed the comments in the code to explain the issue. I think this will do for now.

@plaidpants nice video
@jaredr do you have a video of your toroid view ?

[jaredr]

Some video of the toroid: https://youtu.be/hZl2ixrNMH8

[Fenyx4]

That looks really cool!

[plaidpants]

https://github.com/plaidpants/ANHK-VR

[plaidpants]

Fenyx4 thanks for sharing, looks great.