Pathfinding for enemies

[BenMcLean]

I have been thinking about using the stack to do depth first search pathfinding for enemies to get around playfield obstacles when chasing the player. If it ran out of stack space before finding the player then it would throw the search away and revert to some simpler rule set for it's next move. I would try to have it get closer to catching the player within the limits of the Atari 2600's stack by biasing the search in favor of moving towards the player. (always searching in that direction first) This might enable it to get around at least some simple obstacles intelligently. Is this doable? Has it ever been done in an Atari 2600 game? (I haven't actually played all that many)

 

(later edit) Or wait ... the search should be backwards from what I said. It should push the path from the player's position to the enemy's position so that the enemy can pull it's next destination coordinates in the order it needs to follow.

Edited September 3, 2014 by BenMcLean

[bogax]

I have been thinking about using the stack to do depth first search pathfinding for enemies to get around playfield obstacles when chasing the player. If it ran out of stack space before finding the player then it would throw the search away and revert to some simpler rule set for it's next move. I would try to have it get closer to catching the player within the limits of the Atari 2600's stack by biasing the search in favor of moving towards the player. This might enable it to get around at least some simple obstacles intelligently. Is this doable? Has it ever been done in an Atari 2600 game? (I haven't actually played all that many)

 

(later edit) Or wait ... the search should be backwards from what I said. It should push the path from the player's position to the enemy's position so that the enemy can pull it's next destination coordinates in the order it needs to follow.

I doubt it will work unless

it's really really shallow.

 

The stack is only, like, 8 deep

at best and the kernel will use some.

Certain options or addons will use some.

 

You might be able to get something

going if you sacrifice some variables

and create a data stack.

 

Either way it will be dependent on what

options you're using and how much of

RAM they use.

 

Might be able to use look up tables.

 

[BenMcLean]

I doubt it will work unless

it's really really shallow.

 

The stack is only, like, 8 deep

at best and the kernel will use some.

Certain options or addons will use some.

 

You might be able to get something

going if you sacrifice some variables

and create a data stack.

 

Either way it will be dependent on what

options you're using and how much of

RAM they use.

 

Might be able to use look up tables.

Random Terrain's web site says, "The DPC+ stack can be used to save and restore your bB variables. There are 256 stack locations available, with the top-most location being #0 and the bottom-most being #255.... Note: The DPC+ stack is a special stack just for you that is 100% dedicated to your push and pull commands. Nothing else uses it. It's all yours."

 

According to this, I should have 256 bytes of stack space that is only for my program, (not used by the kernel) which is used by the push and pull commands. This would be separate from and in addition to the 26 bytes used for variables and the six bytes used for the gosub and return commands. Is that true or not?

Edited September 3, 2014 by BenMcLean

[bogax]

Random Terrain's web site says, "The DPC+ stack can be used to save and restore your bB variables. There are 256 stack locations available, with the top-most location being #0 and the bottom-most being #255.... Note: The DPC+ stack is a special stack just for you that is 100% dedicated to your push and pull commands. Nothing else uses it. It's all yours."

 

According to this, I should have 256 bytes of stack space that is only for my program, (not used by the kernel) which is used by the push and pull commands. This would be separate from and in addition to the 26 bytes used for variables and the six bytes used for the gosub and return commands. Is that true or not?

Ah, well, I know almost nothing of DPC+

If RT says so I'd take it as truth until

proved otherwise.

 

Sounds like you're good to go, let us

know how it works out.

 

(When you say depth first I'm thinking

recursive subroutine calls, but of course,

it doesn't have to be that way and you

could probably manage that with a little

asm trickery)

 

 

[BenMcLean]

(When you say depth first I'm thinking

recursive subroutine calls, but of course,

it doesn't have to be that way and you

could probably manage that with a little

asm trickery)

Given that you can really only go three gosubs deep, (six bytes reserved / two bytes per gosub = three gosubs) obviously I would want to use goto for the recursion in this case, not gosub, and keep track of how deep in the recursion I am with variables. I do plan to use individual gosub/return pairs within each iteration in order to abstract some parts of the algorithm that are used multiple times.

 

I don't think I'd need to write any actual assembly for this. It seems like it should be doable within Batari Basic.

Edited September 3, 2014 by BenMcLean

[bogax]

Given that you can really only go three gosubs deep, (six bytes reserved / two bytes per gosub = three gosubs) obviously I would want to use goto for the recursion in this case, not gosub, and keep track of how deep in the recursion I am with variables. I do plan to use individual gosub/return pairs within each iteration in order to abstract some parts of the algorithm that are used multiple times.

 

I don't think I'd need to write any actual assembly for this. It seems like it should be doable within Batari Basic.

 

Not that I'm advocating it,

 

but there's at least two ways to implement

a computed goto with just a few bytes of asm

(push an address to the return stack and return

or jump indirect)

 

Given that, you could in principle use

the DPC+ data stack as a return stack.

 

(or do direct or indirect threading

write a FORTH in bB )

 

 

[+Gemintronic]

Just opinion here. I apologize in advance.

 

Avoid trying to shoe in modern game theory into an Atari 2600 game. I've had to un-learn using gosubs due to eating CPU cycles. I use roomy/spacious playfield screens to avoid having to worry about pathfinding. When I do, it's typically something like picking new goalx and goaly locations for the enemy and then seek the player again when it reaches those coordinates.

[BenMcLean]

Depth first search isn't really "modern game theory" ... it's just an algorithm and most of the work on it was done in the '70s unless I am greatly mistaken. Anyway, I have come up with a reason why this won't work: there is no fast enough way to check whether or not you've already searched a particular square before in order to avoid going in circles in your search path. You'd have to progress back through the entire stack at each square you search and that would almost certainly be prohibitively expensive. I'll just have to think of something else. Or maybe use a grid with bigger/fewer squares ... hmm. Will keep thinking this over.

Edited September 11, 2014 by BenMcLean

[+Gemintronic]

I guess what I meant is that you're trying to force to 2600 to do things that work on more robust systems. That's OK if that's your primary goal. Otherwise you might have to apply some lateral thinking.