Author Topic: Procedural generation part 2 / Space explorer game  (Read 2251 times)

0 Members and 1 Guest are viewing this topic.

Offline coolsnake

  • LV2 Member (Next: 40)
  • **
  • Posts: 36
  • Rating: +2/-0
    • View Profile
Procedural generation part 2 / Space explorer game
« on: November 05, 2011, 01:12:55 pm »
Here is the first part:
http://www.omnimaga.org/index.php?PHPSESSID=vdu1jt4pj3g1sauc09tcsh89n2&topic=4382.msg61597#msg61597

Recap:
I've always been interested in procedural generation, more specifically the generation of an universe in space.
Last time I posted about this I posted a program that did something like that. You're a little X-spaceship that flies through a dynamically generated universe filled with asterix-stars. It was horribly inefficient/slow and needlessly complicated.

Today after reading a bit about "Movement in Maps","Making Maps" on TI-basic developer I decided to give it another go. I used this code from tibasicdev for the movement.

Code: [Select]
:Output(1,1,Ans
:Repeat K=21 and AB=26   //AB=26 can be changed for different exit point
:getKey→K
:If Ans
:Output(A,B,"_  //One space, checks for key press and erases
:sum(Δlist(Ans={25,34
:A+Ans(" "=sub(Str1,16(A-1+Ans)+B,1→A   //If future coordinate is a space, it moves
:sum(Δlist(K={24,26
:B+Ans(" "=sub(Str1,16A-16+B+Ans,1→B
:Output(A,Ans,"X

While the movement itself was very fluid, a great bottleneck was the generation of a new screen everytime i switched to a new sector. It took up to 7 seconds using a string as the base for my map. While I was able to optimise it up to around 3-4 seconds it was still pretty long. It was a real shame since the string consisted mostly out of empty spaces with some "*"-stars sprinkled in between. I was able to fix it by using a list filled with 0's as a base and randomly put some "*" in there. The result is the generation of new sectors is almost instant now, making the program in total very fast. I added the program in an attachment for those interested :)
The way it's done is very elegant and filesize is almost half of my first attempt.

The way it works is that every screen has its own seed. The calculator then uses this seed to randomly generate a level. If you move one screen to the right, the seed increases with 1, to the left decreases with 1 etc.
LIST.8xp takes care of that and then also generates the level. It makes an empty list of 128 characters(the number of characters that can fit on a calcscreen) and then randomly inserts a star into the list and displays it on the screen.
GAME.8xp is used to start the game. It uses LIST to generate the level and contains the movement loop. It can then use the list to see if the player is bumping against a star or not. When the player moves to another level the loop ends, the new seed number is stored in C and GAME.8xp is recursively opened and then uses LIST.8xp to generate a new level again.

I'm still not able to generate truly unique levels and I don't think i'm able too unless I prerender them all and compare them one by one, which is a bit too calculator intensive. You can have about 10^8 calc screens before changing the seed doesn't matter anymore. The calculator then just keeps displaying the same screen.

Enjoy!

EDIT: tried uploading it again, should work now.
« Last Edit: November 06, 2011, 07:05:16 am by coolsnake »
Unpretty Integrals
This program gives you a graphical representation of the "fnint(" function, which allows you to calculate definite integrals. It is extremely similar to the functionality MathPrint provides, minus the extreme bloat that slows your calculator down to a crawl.

Offline ben_g

  • Hey cool I can set a custom title now :)
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +125/-4
  • Asm noob
    • View Profile
    • Our programmer's team: GameCommandoSquad
Re: Procedural generation part 2 / Space explorer game
« Reply #1 on: November 05, 2011, 03:03:33 pm »
sounds useful for space shooters or other games with big levels. And 10^8 is deffinately a lot more than someone actually needs.

btw: I saw you said that you uploaded it in an attachement, but it doesn't show up.
My projects
 - The Lost Survivors (Unreal Engine) ACTIVE [GameCommandoSquad main project]
 - Oxo, with single-calc multiplayer and AI (axe) RELEASED (screenshot) (topic)
 - An android version of oxo (java)  ACTIVE
 - A 3D collision detection library (axe) RELEASED! (topic)(screenshot)(more recent screenshot)(screenshot of it being used in a tilemapper)
Spoiler For inactive:
- A first person shooter with a polygon-based 3d engine. (z80, will probably be recoded in axe using GLib) ON HOLD (screenshot)
 - A java MORPG. (pc) DEEP COMA(read more)(screenshot)
 - a minecraft game in axe DEAD (source code available)
 - a 3D racing game (axe) ON HOLD (outdated screenshot of asm version)

This signature was last updated on 20/04/2015 and may be outdated

Offline shmibs

  • しらす丼
  • Administrator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2132
  • Rating: +281/-3
  • try to be ok, ok?
    • View Profile
    • shmibbles.me
Re: Procedural generation part 2 / Space explorer game
« Reply #2 on: November 05, 2011, 03:54:17 pm »
i love this concept =D
you shouldn't try to make every single screen unique if you're going for truly random, as things do repeat in a random set. however, if you want to lessen the likelihood of that happening, i guess you could make the screens generated depending on the current seed and the one just after it as well, rather than only one.

Offline coolsnake

  • LV2 Member (Next: 40)
  • **
  • Posts: 36
  • Rating: +2/-0
    • View Profile
Re: Procedural generation part 2 / Space explorer game
« Reply #3 on: November 06, 2011, 07:43:51 am »
There was a tiny bug in the previous file caused stars not to be generated in the 12th and 13th column, I reuploaded the file with the fix.

I might try to generate a truly unique universe sometime. If my math is right you can have up to 18k unique screens with max 10 stars and 48 possible places to put them. I probably would just bruteforce it though. :p
Generate x amount of lists and compare them using sum(abs(L1-L2)) to see if there are any dupes.
That being said, yeah the difference between a truly unique universe and a highly randomised one is neglible. I doubt someone would really take note of every single screen.

Also if you mean to make a truly persistent universe, 10^8 screens are indeed a bit out of your ball park =P

Lists with 128 numbers take about 1000 bytes which means 20ish active lists at any time.
If you make use of the archive that number goes up to 500. Since they mostly consist out of zeroes you can probably compress them to a 10th the size, meaning 5000 sectors in total. Also if you used some programmer magic you could probably atleast double that number, going up to 10000^^

Here are some interesting numbers:
time to generate a sector using the old method with a string: 7-8 seconds
byte size string with length 128: 100ish bytes
time to generate a sector using the new method with a list:0.55 seconds
byte size list with length 128: 1000ish bytes
byte size compressed list with length 10: 100ish bytes

time to compare 2 lists: 0.13 seconds

I think I could drastically reduce the time using a string if I started using a similar method like I used for the list. Start with a String of 128 " " chars and then intersect some "*" in there. While the code would probably be a lot messier than the one for the list, the advantage would be I could potentially save a whole universe to a single string variable (since the max of a string is limited by ram). Using lists I would be capped at 999 items per list.
« Last Edit: November 06, 2011, 07:44:21 am by coolsnake »
Unpretty Integrals
This program gives you a graphical representation of the "fnint(" function, which allows you to calculate definite integrals. It is extremely similar to the functionality MathPrint provides, minus the extreme bloat that slows your calculator down to a crawl.