Messages

16

Programming / Re: Can someone explain "Dijkstra maps" to me, please? Are they even a thing?

« on: March 24, 2016, 09:22:50 PM »

I have loved using dijkstra maps for a while now... so many problems can be solved with them. One interesting application I have used recently was in stair placement on procedurally generated dungeon levels. I created an extremely maze-like map and wanted to find the furthest point from the up stairs so I could place the down stairs there. A dijkstra map allowed me to do this. Such maps can similarly be used to gauge how "fun" an area of the dungeon is, by mapping the distance to the closest objects that contribute to "fun" (traps, treasure, secret doors, enemies... etc.) And using this measure, you can ensure you don't have any extremely boring parts to your generated dungeon.


This link was mentioned above, but I would like to emphasize it as an easy place to learn about why you would want to use dijkstra maps. I really like the Dijkstra maps visualized article on roguebasin. *two thumbs up*

Thanks, and happy programming!

17

Programming / FOV algorithm demonstration

« on: March 24, 2016, 09:07:34 PM »

I was not satisfied with the naive FOV algorithm I was using for my current RL development in javascript, so I rummaged around the roguebasin wiki and found an article titled Pre-Computed Visibility Tries. This is very similar to something I had done a little work on about 5 years ago, but hadn't gotten results I liked... so I thought I would attempt again. My last attempt involved casting rays to the perimeter of the circle instead of to the edges of a box containing the circle. This is a very subtle, but important difference. (The article explains the difference in full, so I will leave that as an exercise to the reader)

The naive algorithm, which this is replacing, involved dividing a circle into arcs of a small size. (I think I was using about 1 degree arcs), then using the obtained deltaX/deltaY from cos/sin to simulate a light beam until it reached the length of the sight radius, or hit something and died. This method was extremely expensive, requiring about 18ms to complete even when in relatively enclosed spaces. Only because it was a turn-based roguelike was it usable.

I have finished implementation of the new algorithm and found it runs at < 1ms rates for a completely open sight radius of 15(approximate area of 700 tiles) vs the old method running on a sight radius of 8(approximately 200 tiles). Most of the speed here is a massive reduction in redundant tile checking, and using a cache to store each individual ray along with distances for each tile in each ray.

I created an account on the roguebasin wiki so I could update the article with an implementation section. I further intend to write a few articles for the roguebasin wiki, as I have had quite a lot of great ideas out of reading the articles stored there.

I have a test up on my website if anyone would like to "see it in action". The code is also plainly visible to anyone who inspects the source.

javascript LOS test

18

Design / Re: Considering when to generate random map details, all at once or as needed?

« on: March 17, 2016, 06:44:16 PM »

Slight necro up there, but this is one of my favorite topics, so I thought I would comment, too. I personally prefer the method of keeping 2 main rngs. The first would be for level generation, the second for everything else.

With Strife(which I am planning to get back into), I have a basic world structure that gets generated upon starting a new game... an overworld is generated by randomly choosing n spots across the map, where n is a random number inside a certain set of bounds, and is chosen as the first thing after the map seed is set. These represent seeds of random terrain features called regions(mountain, lake, plain, forest, desert, swamp, volcano) which are chosen using weights to create an acceptable distribution. (E.g. less volcanoes, more plains) All the map cells are assigned to a region using a voronoi diagram approach.

At this point, I generate the dungeon seeds for all mountain ranges and volcanoes, which are placed in the geometric center of the region. This includes how deep they go and difficulty of the dungeon (chosen based on the starting location of the player), any special rewards, and the seeds for each level. I also generate city seeds for all the regions that were determined to be "bountiful" enough to support a city/town population.

Because I have the ability to generate the level from a seed number, I can easily store level deltas... changed doors, smashed walls... etc. while maintaining a smaller memory footprint. Items, traps and monsters are spawned outside of the seed rng (and consequently have to be saved as additional info about the level), but could easily be worked into the process if you wanted the monsters and items to be the exact same each time you chose a specific level seed. (which I chose not to do)

This allows the ability to play in a familiar world when using the same seed, but make sure that a player can't gain a substantial bonus through brute-forcing the locations of desirable items or artifacts. Anyways, that is the balance that I decided was fair for my game. It will be different for everyone.

I would also like to mention how useful this feature is while developing. I can just manually set the world seed, which allows me to test in the same environment every time... If I encounter an error with map generation, I know exactly how to reproduce it, and i don't have to generate any previous maps before I can get the RNG back into the state that generated the troubled map.

19

Development Process & non-technical / Re: Independant turn based multi player

« on: May 04, 2015, 06:20:39 PM »

for me it's all about having a stack of scratch paper sitting in front of me upon which I can write notes, do psuedo code, draw examples.... make notes of bugs I've found, priorities in my dev work... etc.

When I was writing the liquid code for a terraria-like a couple years ago, it took many iterations before I was satisfied with it. I wasn't able to come up with an algorithm that I liked until I decided to work out the test cases on paper.

20

Programming / Re: Different methods for loading/saving

« on: April 13, 2015, 09:49:57 PM »

I'm still a bit confused by the record/playback saving model. If you have thousands of turns will the code have to go through them all one by one resolving them each time? It seems like it might be quite an inefficient way of doing things with AI and everything, also I imagine any bugs at all would cause a lot of issues as the rest of the playback would be broken from that point on. I can't seem to get my head around the idea properly. I have got an animation system in place, but it would be possible to add a "playback" flag which skips to the end of any animations without playing them so I think it would still be possible.

I have managed to implement a different load/save method that seems to work ok.

Each class has a create() and a restoreFromSave(_saveObject) method.
The first one is used when creating the object for the first time and the second when restoring from a save file.

It seems to work without too many problems, but every single new variable I add to each class needs to be stored and reloaded properly which is a bit of a pain. Is that normal for a game of this type?

I am writing the game in Javascript which doesn't have a way of serialising "classes" unfortunately. I'm not really using much OOP to be honest, just have javascript style "classes" that can store data and contain functions as well which I've realised can't all be saved together.

I too am developing roguelikes in javascript. My project (strife) has been developed with a very similar method of load/save implementation. Here is an example of a class that I load/save: https://github.com/gregbillings/strife/blob/master/src/js/resource.js.

I have a central function that performs the basic copy for all savable objects. (https://github.com/gregbillings/strife/blob/master/src/js/jsRL.js#L728)

Each "class" keeps a list of shallow fields that are trivially copyable. The save/load functions on the class take care of the other variables (usually savable classes/arrays themselves). the 'constructor' for the class also includes a check to see if the first passed variable is actually a saved instance. If so, we pass it through to the load function. This results in being able to pass a saved version of the object when instantiating a new instance of the object in question.

e.g.

Code: [Select]

//create new object
var life = new jsRL.resource('HP', 'red', 15, 15, 1 / 800 ); //name, color, max, current, recovery rate/time

//save the object:
var save = JSON.stringify(life.save());
//save now looks like this: "{"name":"HP","displayColor":"red","current":15,"max":15,"recoveryTime":{"base":0.00125,"delta":0},"recoveryBucket":0}"

//restore object
life = new jsRL.resource(JSON.parse(save));

This way, adding a trivial variable with a basic data-type is easily done by simply appending it to the list of shallow variables specific to your class you are saving/loading. While still annoying, it is significantly less so than a pure ad-hoc implementation.


As for random number generation: I found a useful prng called seedrandom (see https://github.com/gregbillings/strife/blob/master/src/js/seedrandom.js for the copy I use.) It allows you to instantiate a new random with a given seed to always get the same results. With some modifications, it could be made to allow you to save it's current state into a json object to be saved and loaded again at a future date.

As far as securing the environment against a malicious user goes, the javascript environment is a particularly poor choice for attack-resistant implementation.

If people want to play honestly, they will do so, if they don't, they will find ways to circumvent whatever you can throw at them. The only real exception to this is server + dumb client interactions... but that is a topic for another time.

In short, my approach is to assume that if a player wants to scum, or modify their "1d4" sword to be a "1d4+100" sword, they can do that. Hardcore rl players would never do something like that, though... as they are looking to beat the game, not the code.

21

Programming / Re: Programming graphical effects with delays

« on: March 19, 2015, 09:48:02 PM »

for strife, I ended up doing blocking animations and asynchronous animations. The JS code stops executing and does setInterval() to queue up all the graphics changes that will occur in order. After all graphics are finished, the UI is re-enabled and gameplay continues like normal.

e.g. click on the Strife link (below) and type a name or whatever, then press f to enter firing mode and target a square, then hit f again to see the arrow animation.

As for damage and effect notifications that show in-world (e.g. 5 damage or Stunned!) those are asynchronous and are actually just html with css transitions that move them up the screen.

22

Design / Experience Point cost per level

« on: October 31, 2014, 05:23:37 PM »

So, for the last 2 years or so I have been using a fairly simple method of defining how many experience points are required to reach a certain level. I thought it might be nice to share this method so others could share their thoughts.

To do this, I just set a base experience Requirement. Most commonly, I choose 5.

That means for 5 base exp, it takes 5 exp to reach level 2, 15 more to reach level 3, and 25 more to reach level 4. so by the time you hit level 4, you have gained 45 exp. each level takes 2 * base more exp to reach than the previous level.

It also happens that this method quite nicely leads to an easy total exp formula:

expReq for level n = (((n-1)^2) * baseReq) - currentTotalExp

Levels start at 1.

Total EXP required to reach a given level:

	base 5 xp	base 6 xp	base 7 xp	base 8 xp	base 9 xp	base 10 xp
Level 1:	0	0	0	0	0	0
Level 2:	5	6	7	8	9	10
Level 3:	20	24	28	32	36	40
Level 4:	45	54	63	72	81	90
Level 5:	80	96	112	128	144	160
Level 6:	125	150	175	200	225	250
Level 7:	180	216	252	288	324	360
Level 8:	245	294	343	392	441	490
Level 9:	320	384	448	512	576	640
Level 10:	405	486	567	648	729	810
Level 11:	500	600	700	800	900	1000
Level 12:	605	726	847	968	1089	1210
Level 13:	720	864	1008	1152	1296	1440
Level 14:	845	1014	1183	1352	1521	1690
Level 15:	980	1176	1372	1568	1764	1960
Level 16:	1125	1350	1575	1800	2025	2250
Level 17:	1280	1536	1792	2048	2304	2560
Level 18:	1445	1734	2023	2312	2601	2890
Level 19:	1620	1944	2268	2592	2916	3240

This has so far seemed like a decent linear increase. Of course, the amount of increase in experience needs to be gauged with the amount of experience given by a single monster. in strife, the early monsters give only 1 exp, late-game bosses/elites will(not yet implemented) eventually give up to 100 or so.

This could also easily lend itself to creating player race-types that require different amounts of exp. E.g. the troll race in ADOM requires a ton more exp relative to the grey elf race. So, in my case maybe grey elf would be 5 exp base and a troll would be 11 exp base.

If anyone is interested in seeing this system in action, head on over to strife to check it out:
http://www.exilania.com/strife

23

Programming / Re: Loops on dungeon-type levels

« on: October 17, 2014, 09:46:48 PM »

Loops make levels a bit more interesting to explore, or so the players say

@sokol815 thanks, I tried something similar but a bit more brute-forcish and didn't like it much really; after generating the level I was taking a random wall and doing a straight corridor on its normal direction, hoping to hit some other room and then link them... may be aiming for the center would increase the chance of positive links.

You bet! Happy programming!

Why do you want loops? And what kind of loops? Last room connecting to first, or just more than 1 ways to reach a room from another room. Loops can't even be guaranteed depending on your generator.

Loops can easily be guaranteed via this method. The size of the loops is a different matter entirely. 

24

Programming / Re: Loops on dungeon-type levels

« on: October 17, 2014, 08:51:25 PM »

In Strife, I add loops later after generating the normal dungeon like you describe, then going back and picking a random room, then based on where it is on the map, start running a corridor towards the center of the map on a cardinal axis. After it runs outside the room's wall for n tiles without bumping into anything, it makes a 90 degree turn toward the center of the map and either finishes when it hits a room or corridor or it just dies if it becomes too long.

If it happens to run into something else before it makes a turn, it just makes a straight hallway between the two.

25

Design / creating compelling monsters

« on: October 16, 2014, 02:06:25 AM »

I am working on my roguelike strife. And find myself preparing to code a more intelligent ai than my current find player, bump player routine.

monsters are responsible for a large portion of the enjoyment one gets out of a roguelike. What features make those monsters contribute most to the gameplay experience?

Some thoughts that I have gathered from around the forum and a few of my own:

• monsters wield all items the npc can wield (what if a monster picked up an amulet of life-saving, then came back to life after you killed them!?)
• monsters have abilities that make some challenging and others interesting (ratling duelists in ADOM, anyone? - side note, that is a great example, positive and negative effects can come from that interaction.)
• monsters use their abilities intelligently and to great effect against the pc
• some monsters represent a need to tactically think about your choices for how and when to defeat them. E.g. explosion on death, gathering more strength each turn, splitting gelatinous cubes, vampire weak during the day
• monsters that trick the pc (maybe only the first time, but oh man, the feeling of being tricked... ) e.g. the classic mimic
• monsters should not all feel 'samey'/like cookie cutter monsters
• some monsters are just pc fodder

I'm curious to know what other thoughts and experiences you forum members have had in designing monsters that add greatly to your games, or even encounters you have had in other games.

26

Programming / Re: Neohack progress report - I'm being chased by wolves!

« on: October 15, 2014, 05:52:17 PM »

kind of reminds me of an old javascript game I wrote back... in 2010. Called minotaur vs orcs. you are a minotaur defending your maze against an incursion of orcs. The faster you beat a level, the more points you get. Not my best work, but it's what got me started writing roguelikes.

http://exilania.com/minotaur/

27

Design / Re: Wound system

« on: April 29, 2014, 05:22:44 PM »

I like the idea of a wound happening at 25% life, but what if instead of reducing your maximum life, it reduced a stat like strength or dexterity? Then the PC would have to go through "rehabilitation" (e.g. using skills/doing things that exercised the drained stat) in order to gain the points back.

for example, if it was a wound to the head (randomly rolled, like the ship example above), it could greatly affect your intelligence. If bad enough, it could give you statuses like "migraine" or "concussing". Then the PC would have to take some turns to recover those lost stats (abstracted in the game as "rehabilitate") which may trade a serious wound like "concussing" for another like "tired" which then simply requires you to eat food or something similar.

This functionality would only work, though if "time is of the essence", so taking time to heal yourself means you lose some other resource... a quest fails because of a time constraint, you become hungry, radiation/corruption in the area draws your PC towards their death... monsters come and find you as you are attempting to rehabilitate yourself... (probably the most commonly used)... the end-boss of the current area grows in power as you spend more time in the area...

28

Other Announcements / Re: XKCD recognizes Angband

« on: April 25, 2014, 03:14:02 PM »

I am subscribed to Randall's what-ifs as well.

29

Player's Plaza / Re: RL for a 1024x600 netbook and no numpad

« on: April 20, 2014, 09:26:19 PM »

ADOM is a good bet. It is a pretty deep Roguelike, uses only the single console window at 80 x 25, and runs at 738 x 464 on my screen.

you can use the 1 3 7 and 9 keys for diagonal movement, arrow keys for cardinal movement. It's not ideal, but after you have played for a while, it will become second nature.

30

Traditional Roguelikes (Turn Based) / Re: Moria video podcast

« on: April 17, 2014, 05:39:36 PM »

I like the format of this video series. Looking forward to future podcasts. Die Balrog, die!