Out of memory on this line

[LoadError]

FOR C1=2 TO LEN(S$):POKE(I+C1-2),VAL(MID$(S$,C1,1))+118:NEXT:RETURN

This line parses a string (s$) one character at a time, then pokes the numeric value of the character (+118) on the screen starting from a certain location (i). This is used in my game to display numbers (score, lives, level, time remaining) since I am using a redefined charset and I can't use PRINTs.

After the recent edits to the code, this line is now giving me out of memory and I can't understand why.

[Mike]

This is most probably caused by a "pending" stack overflow due to a routine in your program, which errorneously does not return to the caller by RETURN but by GOTO. This fills up the stack, and then triggers the error (slightly earlier and at another place), when a complicated expression is evaluated (which itself also needs some space on stack to be calculated).

See also the thread 'Can a basic function call (FN) cause out of memory?' for a similar discussion.

[LoadError]

Yes, I had found that thread and eliminated a case where this problem was happening, but the out of memory problem continues, so I will have to check again. I have used a lot of gosub statements and quite a few for... Next. Other than this, the main problem is that the pseudo AI routine for the enemies movements slows down the game a lot. I have come at the point that I don't know if I will succeed.

[PhotoJim]

Popping out of a for/next loop will have the same effect on the stack as gosubbing without returning. If you need to hop out of a for/next loop, the correct technique is to assign the for variable to the top value required by your loop, and then execute one last next and then move on, e.g.

10 FOR T=1 to 10
20 PRINT T "BANANAS!"
30 INPUT "ARE YOU DONE";D$
40 IF D$="YES" OR D$="Y" OR D$="YUP" OR D$="OUI" OR D$="SI" THEN T=10
50 NEXT

[LoadError]

Got it, thanks.
I've identified the problem! It was indeed an overlooked circumstance in which a subroutine exited with a GOTO rather than a RETURN. It took a bit of reworking but I eliminated the glitch.
Also the performance drop due to the moving "AI" is not so bad after all, when the game is compiled. But the bad guys, which tax the performance a bit with their pseudo AI, don't move fast enough... I don't know if it's a limit with BASIC performance (albeit compiled) or not. The thing is, all the operations are sequential: on every cycle of the main loop, one of the (min. 2, max 4) bad guys makes a move, and until it is done, nothing else can happen at the same time (hence the slower movements of the "hero"), it's a kind of a catch 22 situation. I will have to let it sit for a while and see if I come up with any idea. I need to both make the enemies faster, so that they are a real challenge, and to make this not slow down the main loop too much.

[Mike]

@PhotoJim: dangling FOR...NEXT loops are also cleared from the stack, when a "new" FOR with the same loop variable is initialised, when the NEXT of an enclosing FOR loop is used with explicitly given loop variable, or when the FOR...NEXT loop is placed within a sub-routine and a RETURN is done 'prematurely'. The interpreter keeps track what parts of the stack belong to GOSUBs and FORs, and also notes down the name of the loop variable along with each FOR.

For this reason, it is much more 'difficult' to fill up the stack with dangling FOR loops than it is with GOSUBs.

So, your technique of assigning the loop variable the last valid value and then jumping to the NEXT command to close the loop works, but isn't strictly necessary.


@LoadError: I'm glad to see you zeroed in on the bug!

The thing is, all the operations are sequential: on every cycle of the main loop, one of the (min. 2, max 4) bad guys makes a move, and until it is done, nothing else can happen at the same time (hence the slower movements of the "hero"), it's a kind of a catch 22 situation.

It might help a lot to reorganise the main loop strictly as finite state machine. Each state corresponds the the movement of one of the figures on screen. When one of the figures doesn't exist, the execution of that state just advances to the next state.

[LoadError]

If I am not mistaken about your suggestion, I had kinda of figured out the same and that is why I used a token system to move the bad robots. At each loop, just one of the robots moves, then passes the token. So in a sense, I'm already kind of there. What is consuming resources, I think, is that I am using a kind of "collision avoidance", i.e. every time a robot moves it scans the neighboring locations (3 to 8 depending on if it's near the edge of the screen or not) to detect which are "free" (free=blank space or, of course, the tasty "good guy") in order to restrict the next movement to one of these locations. There are two kinds of robots, Dumb and Dumber if you pass me the analogy. The dumber type just moves randomly in a vector until it needs to change course (at which point it chooses a random "good" direction), the dumb type in addition to scanning the neighboring location also detects the goodguy's current whereabouts and gives precedence to the "good" direction that will bring it closer to its prey. And this is upon every move i.e. every time the robot has the token. Originally there was no collision avoidance, collisions where detected after the tentative move had been elaborated, and at this point the robot passed the token: this resulted in the robots being still for several consecutive seconds on end, so I switched to this kind of collision avoidance.

[Mike]

O.K.

You could also try to compare your algorithm with the method used in "Zauberwald" in my Games collection. There, two ghosts are chasing the player in the forest. Besides the direct route (vertical, horizontal or diagonal), the method also allows for just vertical or horizontal steps instead of diagonal steps when the direct way is obstructed by a tree. Just take a look at lines 73 to 88 in the listing.

The game keeps a constant pace in the first level by locking away one of the ghosts.

[malcontent]

Correct me if I'm wrong, but it sounds like you're scanning for blocked moves directly after a move to predict the one that will occur later? Far better to just try to move in the direction, figure out you're blocked, and then look for an open direction. Pick a random direction once, and if it's also blocked, fall through (the enemy will pause for one update) then try a random direction again.

Also, per update it could be the player that passes the chase information to enemies, rather than having all the enemies do the check (you could limit it to the nearest one, or nearest two.) If you pass a direction to them, and follow the above idea, they will take a random step if blocked before resuming the chase.

[Forbidden64]

Another way to reduce AI CPU usage is to approach the movement issue from a different direction. I made a game a while back in basic that was a top down scroller for ms-dos. The un-compiled version was rather slow and originally was event based. You press a key and a bunch of stuff happens, then everything stops. My game likewise had stack overflow errors for the same reasons mentioned above...even on an IBM! Eventually I made it real-time but noticed that the way I coded it was extremely inefficient, the stack crashes would happen faster, and generally it was very slow to respond. I cleaned up the code, but one thing I did do if I recall was just have the enemies take turns on the loop.

I presume you are using pseudo-objects/classes by means of concurrent arrays. ex(3) ey(3) eh(3) for enemy number 3, x y and hit points..etc. The trick is to, instead of using a for loop from 1 to total, using an increment in the main program loop, or segmented loop. I will give some examples as well as a pretty neat, and very fast algorithm for AI movement in basic. you can automate the program to find an optimal speed for the enemy movement on a particular system, although the syntax will change slightly, this type of thing is less important on the commodore, where scaling systems just never happened. It would still be useful to be able to change the amount of enemies in an incremental loop based on how fast the game is running through individual loops using the jiffy clock...anyway:

Examples:
100 tt%=0 :rem total enemy class objects in existence.
110 dim ex%(20),ey%(20),eh%(20) :rem max array for enemy pseudo-class allows for 20 enemies from array 0.
120 dim mp$(20)
map defined as 20 lines of text, which can be interpreted into sprite placement data, or actual letters that have been redefined and easily manipulated behind the scenes using the mid$ statement. Additional time can be saved by comparing the projected move to a static like a wall or whatever, as opposed to many different kinds of wall. Better to redefine the walls character definition and use the same letter all the time. also surrounding the screen with walls prevents the extra logic needed to handle them accidentally leaving the game and possibly poking your machine into a crash ( I did that once) and i hadn't saved anything...although it was a petscii graph on a c64.

Examples:
w prints wall redefined, d prints door redefined, space(represented by a dash) prints nothing...i guess...not defined?
maps can be stored in a file and be loaded individually off of sequential files...This saves an enormous amount of space, and allows you to create a massive game with tons of maps and environments. In one game what I did was I had a file that told me how many maps there were. The editor upon making a new map, would append that file, and write a new map file into that index, then save the map data strings out to another file under the name in the index. Thus enabling map editor to seamlessly expand the game. Bosses were a separate routine triggered when you stepped on a certain tile type, new levels or environments were triggered by a stairs up or down, or a gate.

mp$(1)="wwwwwwwwwwwwwwwwww"
mp$(2)="wxwwwwwww-----e--wwwww"
mp$(3)="w--wwwwwwwdwwwwwwww"
mp$(4)="w--------d----e----wwwwwww"
mp$(5)="wwwwww----------wwwwwww"
mp$(6)="wwwwwwwwwwwwwwwwww"
Anyway back to the enemies. Scan the map at map creation, or every so often if it is a scroller.


enemy detect algorithm (based on string map) for the above ascii string array map we just put 6, and 18 across...obviously
for your game you'd use something larger, especially if it is a scroller. x on the map indicates player start location. This setup allows you to use a map editor to create maps and not have to manually define the start location, or randomize it(which can get really unfair if you happen to spawn next to an enemy in a game with one hit deaths).
for i = 1 to 6
for ii = 1 to 18
if mid$(mp$(i),ii,1)="e"then gosub 5000
if mid$(mp$(i),ii,1)="x"then mid$(mp$(i),ii,1)="a":x%=i:y%=ii
next
next

5000 rem ** create baddy (remember tt=0 so thats the first enemy. increment after you create enemy 0
5010 ex%(tt%)=i
5020 ey%(tt%)=ii
5030 eh%(tt%)=int(rnd(1)*20)+10
5040 tt%=tt%+1 rem after creating enemy 0, set the new total to 1 over so the next call in the scan shall be ex(1) etc..
5045 mid$(mp$(i),ii,1)="q" rem once you detect an enemy, replace the scan character "e" with the actual graphic for an enemy, or just a different character if you are using sprites, that way it wont just continually pump out enemies on every scan(another way to eat memory hehe)
5050 return rem obviously on a vic you'd want to crunch this all into one line and save like 20 bytes.

I also chose integers if you noticed because they only take 2 bytes in comparison to 7 bytes for regular variables.
main game loop concept:

now you must save processor time via segmented increments(crunch where possible to save processor time & memory)
500 ts%=tl% rem ts=start increment number. init 0, then old increment top point becomes start
505 if tt%-1>0 then tl%=tl%+int(tt%/4)+1 : rem 25% increment, +1 in case total enemies are < 4
510 if tl%=0 then tl%=tl%+1
515 if tl% > tt% then tl% = tt%: rw% = 1
520 for i% = ts% to tl%
530 gosub 2000: rem enemy movement logic subroutine
540 mid$(mp$(ex%(i%),ey%(i%)="q": gosub 2500: rem re-print new enemy on actual map then call routine to print on screen.
540 next
550 if rw%=1 then rw%=0: tl%=0: ts% = 0


ts% is the start of the current incremental loop. each time it loops, it will start where it left off. tl% is the top of the incremental loop, winding its way toward tt% (total enemies). Once it does, it is reset to 0 and so is ts%. if you have 20 enemies, each loop will only move 5 of them. If there are an odd amount, you can see the algorithm catches them. after it gets to the last of the bad guys, it starts over. You can modify this infinitely until it actually runs as fast as you want. like say 2% of the enemies move per game engine cycle. Although at that point i think Pac-man ghosts would seem like geniuses once you had a lot of enemies. It is also worth pointing out that this algorithm gets more efficient as you add enemies, and less efficient the fewer enemies you have which is a funny emergent property.

A pure incremental version, which is much smaller and simpler is an example of using virtually no flow control at all...saving lots of processing and space. This version would be better for games with fewer enemies, and relies on the simplicity of the routine for speed. The meat and potatoes being only 3 lines!

500 i%=i%+1:if i% >=tt%-1 then i%=0: rem remember that tt% is total enemies + 1 since we increment after enemy discovery.
510 gosub 2000: rem enemy movement logic subroutine
520 mid$(mp$(ex%(i%),ey%(i%)="q": gosub 2500: goto500 rem re-print new enemy on actual map then call routine to print on screen.


Finally we have the AI movement routine...since we have established which enemy is moving before the call, we already know which enemy is moving.
All we have to do is figure out an efficient, but smart as possible algorithm. Once the course is decided, further logic detection is no longer required. Once a move is made, return from the subroutine, and when 3 of the 4 possibilities are eliminated, only one move remains.

erase current enemy.
you x > enemy x, check can move down, enemy move down, return.
you y > enemy y, check can move right, enemy move right, return.
you y < enemy y, check can move left, enemy move left, return.
check can move up, move up, return. (only possibility left, no more logic required)
return anyway, if absolutely no moves can be made.


2000 rem ** enemy ultra fast movement algorithm deployed in basic V2
2010 mid$(mp$(ex%(i%),ey%(i%),1)=" ":d%=0
2020 if x% > ex%(i%) and mid$(mp$(ex%(i)+22),ey%(i%),1)<>"w"then ex%(i%)=ex%(i%)+22:d%=1:return
2030 if y% > ey%(i%) and mid$(mp$(ex%(i)),ey%(i%)+1,1)<>"w"then ey%(i%)=ey%(i%)+1:d%=2:return
2040 if y% < ey%(i%) and mid$(mp$(ex%(i)),ey%(i%)-1,1)<>"w"then ey%(i%)=ey%(i%)-1:d%=3:return
2050 if mid$(mp$(ex%(i)),ey%(i%),-22)<>"w"then ex%(i%)=ex%(i%)-22:d%=4:return
2060 return

Reprinting the enemies is once again a single object job...we have already selected which enemy in the for loop before the subroutine call.
The direction indicator d% tells us which direction the enemy moved, and where to erase the old one. if d%=0, as it is re-initialized each call, no action is taken and the subroutine returns to save processor time. I don't know what character 46 is...so replace 46 with whatever character your enemy is supposed to be. Also the map update routine was left in just in case you are using some other graphics to represent your character, instead of a redefined character.

2500 rem ** print enemies back on the screen
2510 if d% = 0 then return
2520 if d%=1 then poke ex%(i%)*22+ey%(i%)-22,32
2530 if d%=2 then poke ex%(i%)*22+ey%(i%)+1,32
2540 if d%=3 then poke ex%(i%)*22+ey%(i%)-1,32
2550 if d%=4 then poke ex%(i%)*22+ey%(i%)+22,32
2560 poke ex%(i%)*22+ey%(i%),46:return


I also did promise to do a dynamic segment divider too didnt i? using the TI environment variable to see how fast it ought to be? well this post is too long, and Ill have to pull out my reference guide to remember how to use the keywords etc, so Ill put that in another post in this thread. Hope this helps speed up your BASIC proggy! I also hope that everyone who reads this makes a BASIC V2 game (expanded or unexpanded) and posts it so we can have fun playing it !

[Mike]

Code: Select all

if mid$(mp$(i),ii,1)="x"then mid$(mp$(i),ii,1)="a":x%=i:y%=ii

That use of MID$()=... after THEN is not possible in BASIC V2. There exist constructions to express what this MID$() statement is supposed to do for BASIC V2, but they're quite cumbersome.

I also doubt it's speedwise effective to keep an extra, "shadow" screen in the array MP$() anyhow. Everything can be done directly with PEEK() and POKE into the text screen buffer.

[Forbidden64]

Code: Select all

if mid$(mp$(i),ii,1)="x"then mid$(mp$(i),ii,1)="a":x%=i:y%=ii

That use of MID$()=... after THEN is not possible in BASIC V2. There exist constructions to express what this MID$() statement is supposed to do for BASIC V2, but they're quite cumbersome.

I also doubt it's speedwise effective to keep an extra, "shadow" screen in the array MP$() anyhow. Everything can be done directly with PEEK() and POKE into the text screen buffer.

Rats! Well I pulled that and modded it from source I made in Qbasic 4.5 in the late 90's to BASIC v2 and was not aware of the mid$ limitation...the map is present for movement comparison and doesn't get reprinted every cycle. Pokes are used for that part, but I guess super-imposing new bytes into the string might be difficult, and a waste of memory. Better to just use one scan cycle and then leave the strings be. I believe that this would run fast once you factor in the very small enemy movement routine. I already have half a game engine posted up there so I think I'll just finish it and see how well it runs on a 6502. Then I'll post it.

[wimoos]

Hm...you desperately need WimBasic. WimBasic allows Left-MID$ functions, as used here.
Many other features that makes POKEs no longer necessary.

WimBasic can be found at http://wimbasic.webs.com

Regards

[Forbidden64]

Here is a rough draft of the game engine before testing with minimal functionality, no redefined characters or even basic collision detection for enemies. I wonder what other snags and bugs may exist, but this looks pretty sound on the face of it. I'll just have to see if I'm right about the speed.
The spaces don't come out on the map in the forum text, sadly, so the map looks a little screwy. size so far with extra text and some comments is 2.3K. Next to key it into a vic 20 and debug. Wimbasic requires me to burn to an eprom. Such is very good for personal programs, and it actually looks pretty cool! The intention of this little day project is a reasonably fast engine that can run on perhaps an unexpanded, or with some larger stuff added, a 3k, or 8k expansion in pure basic V2 for any old vic-20. This new version omits the need for multi-scan maps.

100 tt%=0
110 dim ex%(20),ey%(20),eh%(20)
120 dim mp$(20)
130 mp$(1)="aaaaaaaaaaaaaaaaaa"
140 mp$(2)="a@1 a2aaaaa e aaaaa"
150 mp$(3)="a aaaaaadaaaaaaaa"
160 mp$(4)="a d5 e6 aaaeaaa"
170 mp$(5)="aaaaaa aaa aaa"
180 mp$(6)="aaaaaaaaaaaaaaaaaa"
190 fori=1to6:forii=1to18
210 ifmid$(mp$(i),ii,1)="e"thengosub2000
220 ifmid$(mp$(i),ii,1)="b"thenx%=i:y%=ii
230 next:next
240 ky$=peek(203)
249 ifky$<>""thengosub2500
250 ifjs%=0thengoto500: rem **joystick input default off
251 S=PEEK(37151):POKE37154,127:T=PEEK(37152):POKE37154,255
252 IF(128ANDT)=0THENifmid$(mp$(x%),y%+1,1)<>"w":Y%=Y%+1
253 IF(16ANDS)=0THENifmid$(mp$(x%),y%-1,1)<>"w":Y%=Y%-1
254 IF(8ANDS)=0THENifmid$(mp$(x%+22),y%,1)<>"w":X%=X%+22
255 IF(4ANDS)=0THENifmid$(mp$(x%-22),y%,1)<>"w":X%=X%-22
256 REM IF(32ANDS)=0 "FIRE BUTTON"
500 i%=i%+1:ifi%>=tt%-1theni%=0:gosub1000
520 gosub1500:goto240
1000 pokeex%(i%)*22+ey%(i%),32:d%=0
1020 ifx%>ex%(i%) and mid$(mp$(ex%(i%)+22),ey%(i%),1)<>"w"then ex%(i%)=ex%(i%)+22:d%=1:return
1030 ify%>ey%(i%) and mid$(mp$(ex%(i%)),ey%(i%)+1,1)<>"w"then ey%(i%)=ey%(i%)+1:d%=2:return
1040 ify%<ey%(i%) and mid$(mp$(ex%(i%)),ey%(i%)-1,1)<>"w"then ey%(i%)=ey%(i%)-1:d%=3:return
1050 ifmid$(mp$(ex%(i%)),ey%(i%),-22)<>"w"then ex%(i%)=ex%(i%)-22:d%=4:return
1060 return
1500 ifd%=0thenreturn
1520 ifd%=1thenpokeex%(i%)*22+ey%(i%)-22,32
1530 ifd%=2thenpokeex%(i%)*22+ey%(i%)+1,32
1540 ifd%=3thenpokeex%(i%)*22+ey%(i%)-1,32
1550 ifd%=4thenpokeex%(i%)*22+ey%(i%)+22,32
1560 pokex%*22+y%,6:return
2000 ex%(tt%)=i:ey%(tt%)=ii:eh%(tt%)=int(rnd(1)*20)+10:tt%=tt%+1
2500 rem ** keyboard move subroutine
2505 pokex%*22+y%,32
2510 IFky$="d"thenifmid$(mp$(x%),y%+1,1)<>"a":Y%=Y%+1
2520 IFky$="a"thenifmid$(mp$(x%),y%-1,1)<>"a":Y%=Y%-1
2530 IFky$="s"thenifmid$(mp$(x%+22),y%,1)<>"a":X%=X%+22
2540 IFky$="w"thenifmid$(mp$(x%-22),y%,1)<>"a":X%=X%-22
2545 poke x%*22+y%,1
2550 return


not implemented
;change character set
; data statements
; move character pointer

;check collision
; if your space = enemy space, enemy dies
; kill array::set x y h 0
; garbage collection
; if enemy at 0 then reorder all, subtract total enemy by one.
end not implemented

240-256 & 2500-2550:
added lines
add movement for main character
getin char
onkey gosub return
add quit option
change character pointer to original location
end of subroutine.

[Forbidden64]

I do have a prominade c1 and a few tubes full of 2764 eproms...so I definitely will be making a Wimbasic cart