TI-83 Calculator Roguelike (not too ambitious)
Arthur J. O'Dwyer
Hello, Usenet. This is my first time posting to a newsgroup,
so let's hope it goes well.
I have programmed a simple roguelike for the TI-83 graphing
calculator (in TI-Basic), whose code can be found at
http://www.ticalc.org/archives/files/fileinfo/251/25142.html
What I was wondering is whether anyone has any good ideas for
*SMALL*, *NON-MEMORY-INTENSIVE* algorithms for dungeon generation,
monster A.I., object generation, things like that. The current
game is pretty slow, and the monsters are next-to-comatose
because they can't afford to look very far for the player --
the farther they see, the slower the game runs.
Just fishing for feedback here... if you don't have a TI-83,
you can prob'ly ignore this post.
-Arthur
Peter Hall
>
> Hello, Usenet. This is my first time posting to a newsgroup,
> so let's hope it goes well.
>
Seems OK so far.
> I have programmed a simple roguelike for the TI-83 graphing
> calculator (in TI-Basic), whose code can be found at
>
> http://www.ticalc.org/archives/files/fileinfo/251/25142.html
>
Congrats on getting this far, many don't, though I haven't checked out
the site, not having a TI-83 and all...
> What I was wondering is whether anyone has any good ideas for
> *SMALL*, *NON-MEMORY-INTENSIVE* algorithms for dungeon generation,
> monster A.I., object generation, things like that. The current
> game is pretty slow, and the monsters are next-to-comatose
> because they can't afford to look very far for the player --
> the farther they see, the slower the game runs.
>
Some ideas:
Dungeon generation: Have a few, say 10-12, pregenerated tilable rooms,
pick a few at random and join them up for each level. Alternately each
level could just be one big open room with a few monsters, a few items,
and one staircase going each way.
AI: Tell each monster where the player is. They would then attack if
possible, or move closer if not. If you dont want it to seem that each
monster knows where the player is then have monsters that are far from
the player ignore that information and move about randomly, or maybe
even go for items, or attack other monsters.
> Just fishing for feedback here... if you don't have a TI-83,
> you can prob'ly ignore this post.
>
Sez who.
> -Arthur
--
Peter Hall
Currently studying *laugh* for his BSEng at ANU
Bureaucracy cuts red tape... lengthwise
Arthur J. O'Dwyer
On Fri, 1 Nov 2002, Peter Hall wrote:
>
> "Arthur J. O'Dwyer" wrote:
/snip/
> > I have programmed a simple roguelike for the TI-83 graphing
> > calculator (in TI-Basic), whose code can be found at
> >
> > http://www.ticalc.org/archives/files/fileinfo/251/25142.html
> >
/snip/
> >
> > What I was wondering is whether anyone has any good ideas for
> > *SMALL*, *NON-MEMORY-INTENSIVE* algorithms for dungeon generation,
> > monster A.I., object generation, things like that. The current
> > game is pretty slow, and the monsters are next-to-comatose
> > because they can't afford to look very far for the player --
> > the farther they see, the slower the game runs.
> >
>
> Some ideas:
>
> Dungeon generation: Have a few, say 10-12, pregenerated tilable rooms,
> pick a few at random and join them up for each level. Alternately each
> level could just be one big open room with a few monsters, a few items,
> and one staircase going each way.
>
> AI: Tell each monster where the player is. They would then attack if
> possible, or move closer if not. If you dont want it to seem that each
> monster knows where the player is then have monsters that are far from
> the player ignore that information and move about randomly, or maybe
> even go for items, or attack other monsters.
Well, here's some more information about the TI-83's capabilities. It
has a Z80 processor (6 MHz) with about 27K of RAM. The programming
language is something like BASIC, including some sophisticated list and
matrix commands. The display screen is 95H x 63V pixels, and includes
both a 8x16 "text mode" and a "graphics mode" with a smaller proportional
font, which I'm using for the game's display.
You see the difficulty of the problem, I hope:
First of all, we have only a very small screen on which to display the
dungeon. (The current "dungeon map" is 6x14 tiles.)
Second, we have somewhat limited data storage.
Third, and most important, we have a 6MHz processor running an
interpreted language, which means we need *really* fast algorithms.
The current dungeon-generating algorithm goes something like this:
Fill the 6x14 map with wall tiles.
Divide the map into fourths vertically.
Pick two points in different "fourths" and connect them with floor
space.
Pick a third point in a different "fourth" from the second, and
connect it to the second with floor space.
Repeat the connecting process several more times.
We end up with a map containing a long corridor that writes over
itself several times, possibly creating a loop or branches.
Place one down staircase at a randomly chosen blank space
(in a different "fourth" from the player's position, if possible).
Choose some random squares and put monsters in them, if they contain
floor tiles.
Place an up staircase at the player's current position.
This algorithm is pretty good. The one that needs work, unfortunately,
is the one that I can't really remember at 3:00 AM. I'll write it up
tomorrow - "monster AI."
-Arthur
Isaac Kuo
>Well, here's some more information about the TI-83's capabilities. It
>has a Z80 processor (6 MHz) with about 27K of RAM. The programming
>language is something like BASIC, including some sophisticated list and
>matrix commands. The display screen is 95H x 63V pixels, and includes
>both a 8x16 "text mode" and a "graphics mode" with a smaller proportional
>font, which I'm using for the game's display.
That's rather powerful, compared to a Commodore 64 (well,
except for RAM). I think I can apply my ancient C64
experience here...
>First of all, we have only a very small screen on which to display the
>dungeon. (The current "dungeon map" is 6x14 tiles.)
You can and should implement scrolling.
First off, the "map" should be a 1 dimensional array. I'm
not familiar with TI Basic, but if it's like Microsoft BASIC
(the old one on the C64), then an array of 2 byte integers
is good. A 32x32 dungeon map is still only 2K in size at
2 bytes per cell.
The contents of the array start off at the top left and go
to the right, wrapping from right to left and going down a
line. For example, element 0 to 31 are the first line,
1 to 63 is the second line, and so on.
Now, all coordinates are single integers--just an "xy"
coordinate rather than an x coordinate and a y coordinate.
This makes a lot of things take half as much space and a
lot of calculations take half the time. This will reduce
your code size also!
The contents of the dungeon map array should be something like:
0 = empty space
1-31 = object
32+0 ... 32+31 = monster/player
99 = wall
100 = some monster/player on top of some object
In addition to the map array is an array of objects (size 28)
and an array of monsters (size 32). This should include
the object/creature type (the displayed character), its current
XY position, and it's hit points or charges (if a wand) or
quantity (if another type of item). A similar array stores
the player's inventory. The player is considered a monster
and is in the monster array.
A useful extra piece of information is "velocity". Velocity
is an XY measure of which direction the creature moved on
last turn. Assuming the monster keeps moving in the same
direction, all you have to do to move it is something like:
if map(currentXY + velocityXY) < 32
//the new space is unoccupied, so let's move!
//first, remove the monster from the current position
if map(currentXY) = 100
...special case of overlap handled by searching...
...object list for what is underneath the monster...
else
map(currentXY) = 0
endif
//second, update the current position
currentXY = currentXY + velocityXY
//third, add the monster to the new position
if map(currentXY) = 0
map(currentXY) = monsternumber + 32
else
map(currentXY) = 100
endif
endif
This makes the AI calculation costs very low for monsters
which are just moving in straight lines. What you can do
is make it so that a monster will just keep moving in a
straight line until either its path is blocked or a particular
turn is reached.
For example, let's say the player is 10 spaces away. The
monster might set itself to chase the player but set a
timer alarm for 5 turns in the future. 5 turns from now,
the monster's AI will try to figure out if there's a better
way to get to the player.
The "bug" with this AI is that the monsters will often fail
to react to the player's moves in a perfect manner. This
"bug" can be considered a "feature" in giving the player a
chance to shake off monsters which are dumber or less
maneuverable. In the mean time, what appears to be a complex
"feature" is actually saving you a bunch of CPU cycles!
>The current dungeon-generating algorithm goes something like this:
[snipped]
>This algorithm is pretty good.
Hey, it works, that's great!
>The one that needs work, unfortunately,
>is the one that I can't really remember at 3:00 AM. I'll
>write it up tomorrow - "monster AI."
Maybe the above suggestions will be helpful.
Oh--you do NOT want to be scanning the map one block at a
time and handling things on a block by block basis. Besides
the difficulties with what to do about a monster moving
down or right (into unscanned territory), it's extremely
wasteful of CPU cycles. Instead, scan through the monster
list.
The basic AI will often need to strip packed XY coordinates
into separate X and Y coordinates in order to calculate
which of the 8 directions it wants to move in. However,
if the monster is actually neighboring the player, this
shouldn't be necessary. Assuming a map width of 32, the
following can work:
relativeXY = playerXY - currentXY
if relativeXY >= -33 and relativeXY <= +33
if relativeXY < -1
if relativeXY <= -31
***player is neighboring!
else
***player is not neighboring
endif
else
if relativeXY > 1 and relativeXY <31
***player is not neighboring...
else
***player is neighboring!
endif
endif
endif
This merely checks if the player is in a neighboring
square. If so, the monster can attack the player.
Otherwise, the AI will have to split up the XY coordinates
to calculate the proper chase direction.
Isaac Kuo
R. Alan Monroe
>> > *SMALL*, *NON-MEMORY-INTENSIVE* algorithms for dungeon generation,
>> > monster A.I., object generation, things like that. The current
>Well, here's some more information about the TI-83's capabilities.It
>has a Z80 processor (6 MHz) with about 27K of RAM. The programming
>language is something like BASIC, including some sophisticated list
I know this isn't much to go on, but I read a library book, years ago,
about making adventure games on the TRS-80. The book was packed with
loads of optimizations for this type of game in a very small
environment. If you can find it, it would be a huge help. Sorry I
don't have a title or author. The focus of the book was games in the
style of Atari 2600 Adventure.
Alan
Dave Slutzkin
> The current
> game is pretty slow, and the monsters are next-to-comatose
> because they can't afford to look very far for the player --
> the farther they see, the slower the game runs.
How are you doing this? Some thoughts:
You should just have to check the distance between the player and the
monster - if it's greater than the monster's sight range then you can
stop. Otherwise, you have to cast a ray to check sight.
This check should just be two multiplies and an addition, cause you can
check against the squared sight range.
You could have some early-outs. If the horiz distance or the vert
distance is greater than sight range, that's an early out.
You could give the monsters delayed reactions for this. So if they
looked for the player last turn, they don't need to look this turn. They
can only look every N turns. You'd need to stagger these so the entire
load wasn't all at once. Maybe keep a counter in each monster, although
this takes memory. Or you could have it less deterministic - if you have
a pointer just check the LSB of the pointer and if that matches the LSB of
the counter then check. This gives you every 2 turns.
I hope some of this makes sense.
Dave.
Arthur J. O'Dwyer
On Sat, 2 Nov 2002, Dave Slutzkin wrote:
>
> On Wed, 30 Oct 2002, Arthur J. O'Dwyer wrote:
>
> > The current
> > game is pretty slow, and the monsters are next-to-comatose
> > because they can't afford to look very far for the player --
> > the farther they see, the slower the game runs.
>
> How are you doing this? Some thoughts:
>
> You should just have to check the distance between the player and the
> monster - if it's greater than the monster's sight range then you can
> stop. Otherwise, you have to cast a ray to check sight.
(Actually, I don't even care about line-of-sight. Adding that would just
slow the game down even more. The player can see everything, and so can
the monsters.)
Here's the code as it stands, with my comments in <<...>> (which hopefully
will clarify the very-dense code in a language unfamiliar to most on this
newsgroup):
<< We have 27 single-char variables (A-Z and Theta), an essentially
infinite number of programmer-defined lists, 10 matrix variables
labeled [A] to [J], and 10 variable-length string variables Str0 to
Str9. List indexing starts at 1, not 0. >>
<< Initialize the monster stat tables; each monster has X attacks
doing YdZ damage on a hit, and has W hit points. >>
{2,4,8,15,24,40,60,80,100} -> listW << this is assignment syntax >>
{1,1,1, 2, 3, 2, 2, 3, 3} -> listX
{1,1,2, 2, 2, 5, 3, 4, 4} -> listY
{1,2,3, 2, 2, 2, 5, 4, 5} -> listZ
<< The dungeon is 6x14 tiles in size >>
{6, 14} -> dim([D]) << sizing the matrix >>
<< A matrix or list element is a floating-point number, not an int.
I assign floating-point values to the dungeon matrix as follows:
100 or greater: wall tile
10s digit: nothing
1s digit: monster present
fractional part: object present
Objects are coded as tval/sval pairs, as in Angband. E.g., 0.1 is
the code for the sword tval, and 0.14 is a dagger (1d4). 0.15 is a
staff (2d5). 0.16 is a sword (3d6), et cetera. 0.2 is the armor tval.
0.3 is the helmet tval, 0.4 footwear, and 0.9 treasure. 0.0 is the
tval for dungeon features (stairs), that cannot be picked up.
(Incidentally, the TI-83 has no integer operations as such, so using
a matrix of integers would *not* speed up the game.) >>
<< The dungeon generation algorithm has already been covered. >>
<< Initialize globals >>
5 -> H : 5 -> I << HP and MaxHP >>
2 -> S : 2 -> T << SP and MaxSP (unused but reserved) >>
0 -> E : 1 -> L << Exp and ExpLevel >>
1 -> D << Current dungeon level >>
0 -> A << Armor class (AC); higher is better >>
<< The player is at position (X, Y) in the 6x14 map >>
3 -> R
<< Variable 'R' holds the "noise radius" of the player for this turn.
Monsters within radius 'R' tiles of the player will get a chance to
move this turn. Fighting increases 'R', so that battle should attract
other monsters. I use a noise radius instead of line-of-sight because
LOS is much more difficult to calculate than a simple circle around
the player. >>
Repeat until Q != 0 << the player quits the game >>
<< Check for experience level jump >>
If L != int(cuberoot(1+2E/3)):Then
L+1 -> L
I + int(L*randNorm(3,0.5)) -> I << randNorm(mean, sigma) >>
Disp "YOUR SKILLS IMPROVE!"
End
<< Regenerate 0.25 HP per turn >>
H + 0.25(H < I) -> H << conditionals return 0 or 1 and
are much faster than If:Then's >>
<< Display the map; code omitted >>
Repeat until Z=0 << Z: whether the move was a "non-
move", like checking inventory or
trying to move into a wall >>
0 -> Z
<< get player's keypress; code omitted >>
3 -> R << "noise radius" >>
<< Move the player; if he's moved into a monster, call the following
routine to hit the monster! >>
Lbl FI << fight the monster at coords X,Y >>
4 -> R << make more noise >>
int([D](X,Y)) -> MonTemp
<< call routine to describe monster MonTemp; omitted >>
Ans -> Str1 << the monster's name >>
<< Does the player miss the monster? Lower miss probability for
desperation (low HP) and skill (high ExpLevel). >>
(0.5) * (1 + (H/I)) * (0.05 + 0.65e^(-L/8))
If (rand < Ans):Then
Disp "YOU MISS THE " + Str1 + "."
<< Now it's time to explain how I track a relatively large number
of monsters given only 27 variables. I know I could use a bunch of
lists, but you also have to remember this is a graphing calculator,
and the user may very well already have important data in a list we
want to use. Plus, there's a lot of code overhead to get data in
and out of lists. So:
The monsters are represented simply as their numbers in the dungeon
map matrix [D]. There is *no other information* stored with individual
monsters; whether they're awake, asleep, moving, dying... all that is
irrelevant.
What I do keep track of is the two variables M and N. M stores a
monster number (the ones digit of a matrix entry), representing the
monster the player is currently "fighting". N stores that monster's
hit points. So as long as the player is whaling on, e.g., a Kobold
or Kobolds, he'll be killing them. But if he stops to hit a Dragon,
M takes on the value of 'Dragon' (literally 9), and N goes back to
100 hit points. The next time he hits a Kobold, M will become 'Kobold',
N will go back to 8 HP, and all his work on the Dragon will be "lost".
I hope that's clear.
Remember, the game doesn't track *where* the current monster 'M' is,
it just tracks *what kind* of monster it is. >>
If not(M):Then
MonTemp -> M
listW(MonTemp) -> N
End
Else
Disp "YOU HIT THE " + Str1 + "."
<< (Find the player's wielded weapon) -> W >>
randInt(W, 6W)
If W<3: randInt(W, W*(W+3))
If W=0: randInt(1,3)
Ans -> Z << The damage goes into Z for now >>
If not(M):Then
MonTemp->M << New current monster >>
listW(MonTemp)-Z -> N
Else: If M != MonTemp: Then
If Z < listW(MonTemp): Then << New monster, unless... >>
MonTemp -> M
listW(MonTemp)-Z -> N
Else << unless we killed it >>
Disp "YOU HAVE SLAIN THE" + Str1 + "!"
E + MonTemp^2 -> E << experience gain >>
fPart([D](X,Y)) -> [D](X,Y) << delete monster from map >>
End
Else << keep whaling on the old 'M' monster >>
N-Z -> N
End:End
If (M) and (N<=0):Then << did he kill it? >>
Disp "YOU HAVE KILLED THE " + Str1 + "."
E + 0.75*MonTemp^2 -> E << experience gain >>
fPart([D](X,Y)) -> [D](X,Y) << delete monster >>
If ([D](X,Y) = 0) and (rand < 0.25):Then << create item >>
1 + iPart(D*rand*rand) -> K
randInt(1,9) -> Theta << K is tval >>
If Theta >= 5: 9 -> Theta << Theta is sval >>
If Theta-1 = (K>4): 4 -> K
If (K < 2 and Theta=2) or (K>2 and (Theta=3 or Theta=4)): 2->K
If Theta=9 and K < 20: 0->K
min(K, 9) -> K
0.1*Theta + 0.01*K -> [D](X,Y) << drop the item >>
End
0->M << The current monster is DEAD! >>
5->R << The fighting makes noise. >>
End
End
0->Z << The fighting takes a turn. >>
<< Back to the main code. I omit a lot of code for picking up and
dropping items, checking inventory, and wielding and removing armor
and weapons. Descending stairs also omitted, but it basically just
sets a flag to create a new level map at the top of the main loop. >>
Else:If ...
Else:If ...
Else
Disp "INVALID MOVE!"
1->Z << don't take a turn >>
End
<< Here is the code for monster AI. It is a scan through the map
looking for monsters,
For(J, 2, 5) << for (j=2; j<=5; j++) >>
For(K, max(2,Y-R), min(13,Y+R)) << the horizontal "early-out" >>
If Q: 13->K << If player is dead, exit loop early >>
int([D](J,K))
If Ans != 0 and Ans < 100: Then
Ans -> MonTemp
(J-X)^2 + (K-Y)^2 -> W
If W <= R^2: Then
<< Call the following routine to move around or try to hit the player.
The monster is at coords (J,K), and the player is at (X,Y). The
distance from monster to player is in variable W. >>
Lbl MF
1 -> Z
If W=1:Then << the monster is right next to player; try to
hit him >>
0 -> Z
<< (describe the monster) -> Str1 >>
For (Theta, 1, listX(MonTemp)) << iterate through X attacks >>
1/8
If (M): 1/sqrt(N) << probability of a miss >>
If (rand > Ans): Then
H - e^(-A/8)*randInt(listY(MonTemp),
listY(MonTemp)*listZ(MonTemp)) -> H << adjusted for AC >>
Disp "THE " + Str1 + " HITS!"
If (H<0):Then << HP drop below zero >>
Disp "YOU DIE."
2->Q << quit >>
End
Else
Disp "THE " + Str1 + " MISSES." << it misses the hit >>
End
End << end of For loop >>
Else << (W>1); try to move towards the player >>
0.5*randInt(0,4) << a random direction >>
If MonTemp=M: N < 0.1*listW(M) << toward or away from player >>
int(2*(Ans+1/pi*angle(X+Yi-J-Ki))) -> C
<< C holds the direction for the monster to move, where 0 is south,
1 is east, 2 is north, and 3 is west. angle(cplx) is a built-in
function that does the same thing arctan() would, only a bit faster.
The net effect: healthy monsters matching 'M' move toward the player,
weak ones retreat, and monsters not matching 'M' move randomly.
It's not a very good AI, I admit. Needs work. >>
<< try to move the monster in the direction specified by C; code
omitted, since it's trivial. Just return failure if it hits a
wall or other monster; otherwise, modify the matrix and return
success, signified by Z=0. >>
If Z: Then << failure; wall or monster in the way >>
C+1->C << rotate to the left >>
<< try to move the monster in *this* direction >>
If Z: Then
C-2->C << rotate back to the right >>
<< try to move it in *one more* direction >>
End
End
End << of motion code >>
<< Back in the main code; we have finished with this monster;
time to go on to the next one. >>
End
End
End
End
<< Handle creating new dungeon levels >>
End
End
Disp "YOU DIED ON DUNGEON LEVEL ", D
Disp "WITH SCORE", 100*D+E+G
<< clean up variables and exit >>
> You could have some early-outs. If the horiz distance or the vert
> distance is greater than sight range, that's an early out.
I do that, as you can see now. Except I use a player-centered "noise
range", rather than a monster-centered "sight range".
> You could give the monsters delayed reactions for this. So if they
> looked for the player last turn, they don't need to look this turn. They
> can only look every N turns. You'd need to stagger these so the entire
> load wasn't all at once. Maybe keep a counter in each monster, although
> this takes memory. Or you could have it less deterministic - if you have
> a pointer just check the LSB of the pointer and if that matches the LSB of
> the counter then check. This gives you every 2 turns.
Interesting idea with staggered monster searching. Obviously, a counter
for each monster won't work without a major rewrite, but I guess I could
do a similar test somehow.
> I hope some of this makes sense.
Very much. Thanks.
> Dave.
I hope you could follow at least the major points of the program...
-Arthur
Dave Slutzkin
> On Sat, 2 Nov 2002, Dave Slutzkin wrote:
<snipped game code>
> > You could give the monsters delayed reactions for this. So if they
> > looked for the player last turn, they don't need to look this turn. They
> > can only look every N turns. You'd need to stagger these so the entire
> > load wasn't all at once. Maybe keep a counter in each monster, although
> > this takes memory. Or you could have it less deterministic - if you have
> > a pointer just check the LSB of the pointer and if that matches the LSB of
> > the counter then check. This gives you every 2 turns.
(Thinking about it, this doesn't work in general with aligned pointers.
If you have word-aligned pointers with a 2-byte word size, the LSB will
always be zero... But you don't have pointers anyway so it's a moot
point.)
> Interesting idea with staggered monster searching. Obviously, a counter
> for each monster won't work without a major rewrite, but I guess I could
> do a similar test somehow.
You could do it by lines or columns. So the even numbered columns would
check on one turn, the odd numbered on the next, for instance. Or even by
combined lines and columns. This would be best if you can loop by 2
instead of 1. This would be less random, but it should still work OK.
If the loop is just as efficient, it should give a 50% speedup in the AI
code, in exchange for some strange gameplay effects. :-)
> I hope you could follow at least the major points of the program...
Yeah. It's a funny little language. Looks like you've done well.
Dave.
Isaac Kuo
>>>You could give the monsters delayed reactions for this. So if they
>>>looked for the player last turn, they don't need to look this turn. They
>>>can only look every N turns. You'd need to stagger these so the entire
>>>load wasn't all at once.
>You could do it by lines or columns. So the even numbered columns would
>check on one turn, the odd numbered on the next, for instance. Or even by
>combined lines and columns. This would be best if you can loop by 2
>instead of 1. This would be less random, but it should still work OK.
>If the loop is just as efficient, it should give a 50% speedup in the AI
>code, in exchange for some strange gameplay effects. :-)
In order to minimize unusual aliasing effects, it may be better to
split up between left half/right half of the world, perhaps with an
overlap in the middle. For load balancing, it might be worth reserving
a variable to record where the "middle" is, and adjust it right or left
if the load is severely unbalanced.
Of course, you can split into more than just two bands.
Isaac Kuo