Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - Omnomnom

Pages: 1 2 [3] 4 5 6
Programming / Re: Map generation woes
« on: November 15, 2012, 01:40:17 AM »
Your generator somewhat inspired me to write this:

That's the holy grail to be able to make maps like that. I can't figure out how to make a computer think like that though. For example my generator doesn't have any thinking in it, it isn't procedural and it's very random. The room positioning for example is haphazzard (the rooms themselves are hand designed so don't count). A human would be able to think ahead and make the rooms align better, use symmetry and have a plan for the available space and what the rooms should be, both in terms of how they would play in combat, eg could be used defensively, but also what the room is (eg an armory). A human would probably think a medical room should be tucked away near the safe part of a fortress. A computer might put the medical room outside the fortress. Maybe something like a computer controlled dwarf fortress could learn to produce dungeons that serve a purpose.

Programming / Re: Map generation woes
« on: November 15, 2012, 12:55:45 AM »

Could you share some details on your map generator algorithm?

the natural environment is created first - rock and lava (perlin noise). Then the output of that gets fed into the room generator. The room generator is very similar to this:

The room are picked from a fixed set of handmade templates. It would be better if rooms were generated procedurally rather than from a small list of templates, but I have no idea how to do that. Here is an example 7x7 template for a roundish room. Each template is a bitmap file, I decided to use that so I could make them with paint rather than needing to make some kind of template editor. Each pixel of the template is a tile:

The orange pixels are walls but also indicate the best places to put entrances. The generator gives them priority when creating entrances. The white pixels are empty. When placing the template over the map empty areas are not hit tested against existing structures or lava which means even though the templates are always square or cuboid the circular templates are really treated at circular, but there's just overhead of the unused empty tiles.

Everything on the map is from templates linking together at entrance positions. Even the corridors and bridges are templates (although they are dynamically created because they have varying lengths).

One thing I am doing differently from the above link is that the generator doesn't modify the map when a template is placed. Instead the template is placed "over" the map in its own layer. Basically each template has it's own X and Y position on the map and coupled with it's width and height (7x7 in the above example) it's possible to query whether the template has a tile at certain map coordinate and ask what that tile is. This wasn't intentional it just happened because i had to mess about with loading them from a bitmap so they had their own grid anyway and then realized it was easier to just pretend they were hovering over the map rather than building them directly into it and throwing them away. It turns out it makes some things much easier though. It makes it simple to move or remove templates after they are placed without having to revert tiles on the map.

It also separates the building process from the design process.

Also because each template represents a room and has a list of live entrances, they can be used as a connection graph. If a template is at position 20,30 on the map and has an in-use entrance at local coordinates (3,3) then you can find out where that leads by finding which template has an in-use entrance on map tile 23,33. It's messy as a connection graph but it does work (eventually).

Additionally with layers it should be possible to more easily copy-and-paste parts of the map a lot easier. Eg copy 3 connected templates and paste them somewhere else. Whereas doing that with a built map is a lot harder because you have to cut around all the other stuff.

the template placement process:

1. Pick a template at random from the handmade templates. Place the template at a random place over the map. This is the initial room. If the placement is invalid then retry until a valid placement is found. Templates can only overlap each other in some ways (eg share walls and entrances). Templates also can't overlap map tiles that contain lava (although I allow exterior walls to overlap with lava to encourage rooms to fit perch at the edge of lava)

2. Add all possible entrance tiles of the placed template to a global list of candidate entrances. Assign each one a priority. If the template has ideal entrance positions (marked in orange on the template above) give those a higher priority.

3. Choose an entrance candidate X from the global list. Higher priority entrances are picked first. This chosen entrance X will be used to expand a new room off of.

4. Create another template. This template is the new room that will be positioned so it joins to the entrance X of the existing room.

5. Choose a random entrance Y from the new template.

6. Join X to Y by positioning/rotating the new template over the map so that its entrance Y lines up with the entrance X of the existing template. Two options are used (50/50): Either a) join them directly (they will share walls this way) or b) place the new room some distance away and connect X and Y with a corridor.

7. Validate the new template placement (and the corridor if one was placed). If either do not validate (eg they overlap an existing template invalidly or overlap lava) then "give up". Remove the new template (and the corridor if one was placed) and go back to step 3. Before going back to step 3 reduce the priority of entrance X. Doing this suppresses entrances that repeatedly fail to work (perhaps there is insufficient space available) and other entrances are given a chance instead.

8. If the new template was successfully placed then set entrance tile X and Y priorities to zero. They they can't be used again. Go to step 3 to continue building.

For bridges everytime a template is placed a check is made to see if any potential entrances border lava on the map. If any do then a line is traced from that entrance across the lava to the other side. A bridge can only be created between two entrances. So first a room has to be created on the otherside of the lava. If one can't be created then the bridge project is abandoned.

The above process leads to a map without loops. Loops are added at the end as mentioned earlier in the thread.

Programming / Linux
« on: November 13, 2012, 10:37:54 PM »
How much rage is caused if a RL only runs on Windows and not Linux? I just did a check of some RLs I have played recently and they support both.

What sort of % of players are lost by only supporting windows? Is it just people who only use linux who give it the finger or do people who have both also rage on it for assuming everyone has windows? id like to support linux but it's harder to do in c# than say java (i think). Also I would only be making something light like a 7DRL kind of thing but stretched over a year, so maybe then people don't care as much and id get away with it?

Programming / Re: Map generation woes
« on: November 11, 2012, 11:04:29 PM »
Map with loops

The map is generated without loops first and then nearby rooms are connected like in Jo's image. To prevent short loops the generator doesn't connect rooms if there is already a short enough path between them. Backtracking is reduced but it's still there. I guess it can't be totally eradicated.

That big circular flower-like room isn't a generated loop, it's a room template that has a hole in the middle where other rooms usually end up built. I tried out a single square room template darren and it works great, except I have had to disable it for now until I've added the trimming of dead ends.

Crossing the bridge over lava in FOV (clearly inspired by brogue):

40% of the map is lava. It's meant to be an atmospheric feature of the map, but most of it is wasted as from the above image you can see only a small part of the lava is ever seen. Most of the lava is wasted space. I will try adding windows to walls overlooking the lava.

Programming / Re: Map generation woes
« on: November 08, 2012, 08:34:08 PM »
Thanks for the map edit Jo that's clarified the difference between dead ends and loops to me and how to eliminate many of the dead ends.

I hadn't thought about loops being important to reduce backtracking. Maybe it was you Darren who mentioned the importance of loops in one of the roguelike radio episodes or perhaps at the irdc. Someone at least planted the importance of loops in my mind for me to get worried about it, but along the way I forgot the reason why. I was only thinking about loops being useful for running from monsters (which is dumb really as you are just as likely to run into a monster coming the other way). Avoiding backtracking is a better reason for loops.

I'll try bigger rooms. The reason why the 3x3 rooms dominate so much is that as the map fills up a lot of the remaining spaces can only fit small rooms, so that's what happens. I will trying putting some sort of cap on them.

Programming / Map generation woes
« on: November 07, 2012, 11:37:31 PM »
Well woes is too harsh a word, it's fun but having some trouble. This is the kind of map my map generator is currently spitting out.

The red dot is the player. There's a few things to excuse here. Firstly the graphics are just for testing, I am not seriously thinking of solid-color tiles and a red dot for the player. There are also two bugs on the map where corridors wrongly overlap, just ignore those. The rooms are also repetitive I know, they are working off a handful of templates I made for testing. What I want to ask is about the general map layout, ie how rooms connect.

Something seems wrong about it. Maybe it's the graphics but are there too many rooms? Perhaps rooms are too small? I know there is a loop problem I am having a problem with generating loops. Is that a big deal? How important are loops in a roguelike in general?

I am also thinking about the game element of the map, such as adding things like locked doors or raised drawbridges. I know a major problem with those is if the stairs and key get spawned behind a locked door it can mean game over....also along similar lines stair placement. If the stairs are placed away from any loop and you immediately encounter a badass monster and have nowhere to run, that is gameover too. How can I avoid stuff like that? Do I just flood the map with loops? Can there be too many loops?

I have maintained a connection graph of the rooms as I suspect that might be useful, but on the otherhand this is also why I am having trouble with creating loops. The generator uses a strict method of joining rooms to guarantee no rogue connections are made. I suspect to guarantee loops though I will need to just drill through a wall now and again but that means my room connection graph might end up it's like one of those vicious circles of chickens and eggs.

Programming / Re: Procedural Plot
« on: November 01, 2012, 10:55:22 PM »
To avoid the hardcoding lots of outcomes pitfall that Darren points out you could write an algorithm that iterates through all weapons in the game and select the one that does the most damage to the chosen boss when held by the chosen character.

If you are okay with a simple plot that should work fine, but if you want somewhat complex and yet serious plots then it'll probably be much harder. Check out this plot generator for example:

Produces a lot of absurd plots for every good one. You could generate 100 and your brain can easily find the best one, but how does a computer do that? seems to be a difficult problem. Maybe some kind of neural net could be trained to spot the bad ones, or good ones, but I've never done anything like that so wouldn't know.

Programming / Re: Programming habits, standards, and learning.
« on: October 20, 2012, 01:09:52 AM »
I started using VB6, then I switched to C++ because people were calling VB6 names, now I've switched entirely to C#.

Language doesn't matter. Improving programming involves things that apply to all languages. That said, don't use VB6 as it doesn't have some useful OO features and being an old language the documentation, examples and tutorials online are sparse.

The easiest switch you can make, if you really want to leave VB.Net, is to C# as the two are very tightly linked. You'll have to learn new syntax, curly brackets are probably the biggest difference, but that's about it. There are sites with chart comparisons between VB.Net and C# syntax:

Java is similar to C# so getting used to C# should help any adoption of Java.

I wouldn't bother learning C++ unless you are interested in understanding low level memory management and pointers. It's useful to know, but that could be said about a lot of things. A few things I would really recommend are:

1a) Read other people's code that is well known for being written well for inspiration. Don't bother to understand how the actual program works, that takes ages, just read the code to see how they've structured and modularized the source code. Just seeing how things had been broken down into functions and split into different files.

1b) Once you realize how to structure code neatly one big trap is to spend too long doing that and to become unproductive. Strike a balance between spending ages doing things perfectly and being productive. Better to write things untidy and refactor later.

2) Learn OO concepts like inheritance and polymorphism. They aren't necessary, but they can help modularization a lot.

3) Improve at tracking down bugs and fixing them. Aside from using tools like the debugger to help, this really involves grinding on ever occurring bugs to increase XP. Bugs will always happen so getting a routine to hunt their source can be a real time saver. As a bonus 1a) should often help to reduce bugs or make them easier to track down.

Programming / Re: RogueLike in facebook
« on: October 10, 2012, 06:12:50 PM »
Looks like your dungeon has suffered an earthquake

Programming / Re: Trouble implementing A*
« on: October 10, 2012, 05:54:37 PM »
Your lowest-hunting code works. It turns out the reason it's saying 4,6 is the lowest F value node in the open list is because it really is. I stepped through the code in the debugger and noticed AddNeigbhours only adds the first four neighbours to the OpenList:

(4,4), (4,5), (4,6), (5,4)

WTF. So I ran through it again and found the reason is it sets InList to True for the 5th node (which is 5,5), but doesn't reset InList when it checks the rest of the neighbours (5,6), (6,4), (6,5), (6,6), so none of them are added to the open list.

If you set InList to false at the start of each loop it will fix this. You can also skip the (5,5) case just for purity:

Code: [Select]
For intX = -1 To 1
   For intY = -1 To 1
      'skip intX=0,intY=0, it's always self, never a neighbour
      If intX = 0 and intY = 0 Then
         Continue For
      'start by assuming a neighbour is not in the list until it is found
      InList = False

This is one of those bugs I mentioned about being hard to spot.

Another even harder bug to spot is in the Path() method itself:

At the end of the processing for a node you set CurrentX and CurrentY.
CurrentX = LowNode.Self.X;
CurrentY = LowNode.Self.Y;

For the next node processing you then instantiate a new tempnode using CurrentX and currentY.

Code: [Select]
With TempNode
     .Self.X = CurrentX
     .Self.Y = CurrentY
End With

You need to also set the G value of the node too. Eg with something like a new variable CurrentG (or you could set TempNode = LowNode somehow rather than making a new node?). The reason you need the G value to be set is that AddNeighbours needs it (for the parent's G value).

I wouldn't have figured that out just by looking at the code itself. It would take me days to even have a chance of stumbling on it. I only found it again through debugging because once I reached GetScore for the first valid neighbour of 6,6 I noticed hovered over Parent.G and noticed it was set to 0 and I knew (6,6).G should have been 14 not zero. So then it was a matter of figuring out why. Was it being reset or was it not being set at all? I debugged through line by line again slowly to find that it wasn't being set. Stepping through code can be tedious, but it is reliable at tracking down the source of problems. Almost any problem can be tracked this way.


This 5 minute video looks like it explains debugging in visual studio with VB (I haven't heard the speech though as I have no sound here):

For more detailed stuff (much of which I don't know) there are tutorials on using the VS debugger here:

What I do is pretty much what the video shows. I just set a breakpoint and when the program hits the breakpoint I use Step Over (F8) to step to the next line. You can keep hitting F8 to run through the whole program one line at a time, each line it pauses. If you are over a method call then Step Into (F10) will step into that method. At any point if you hover over variables in the code it will show you what the values are at the current time of the paused program. There is also an autos window that automatically lists variables in the current scope and their values (rather than having to hover over them).

Programming / Re: Trouble implementing A*
« on: October 09, 2012, 11:56:04 PM »
It's useful to use the debugger in visual studio to step through code one line at a time and check what the values of variables and the contents of the open and closed lists are at any point. That's the best way to figure out what's going on and when it goes wrong. For example I think if you try this on the current code you will find the nodes added to the open list by the first AddNeighbours call all have the same X and Y value (which is wrong)

The reason for this is you are only instantiating one Node object at the start of the method:

Dim TempNode As New Node

You then add this single instance to the open list multiple times (one for each neighbor). This worked before but now that Node is a class it's a reference type so when you add TempNode to the open list it adds a reference, not the object itself. For each neighbor you are adding a reference to the same object.

A fix is to put the 'Dim TempNode As New Node' line after:

If Not (Y + intY) < 0 Then

That way you at least get a new TempNode object for each neighbor.

Another thing. You've added a check in AddNeighbour to see if the node is already in the open list. It just sets InList = True. But IIRC the A* algorithm requires you update an existing node's G value if the new calculated value is lower than the existing one. Fortunately you've already done all the hard work so I think it's just a matter of a few alterations:

Code: [Select]
'check the closed list first
For Each Node In ClosedList
    If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
        InList = True
    End If

'only check the open list if it wasn't in the closed list
If Not InList
   For Each Node In OpenList
      If Node.Self.X = TempNode.Self.X And Node.Self.Y = TempNode.Self.Y Then
         'if the new node info (path from this parent) has a lower G cost than the
         'existing node info (path from some other parent) then update the
         'node info in the open list to come from us (our path is shorter/better)
         If TempNode.G < Node.G then
            InList = True
            Node.G = TempNode.G
            Node.H = TempNode.H
            Node.F  = TempNode.F
            Node.Parent = ThisNode  'this is new parent
         End If
      End If

After that I suspect it might work, I can't see any other problems (not that means anything, it took me about three weeks to implement A* all the time being unable to spot a dozen or so problems)

Programming / Re: Trouble implementing A*
« on: October 06, 2012, 01:54:17 AM »
A few problems I see.

1) Nothing is ever removed from the open list. When you process a node it should be removed from the open list and placed in the closed list.

2) AddNeighbors should skip over neighbours that are in the close list. Closed nodes are done, never to be edited again.

3) In AddNeighbours if a neighbour node is already in the open list then you need to use that node. Don't create a new Node instance. Each tile should have at most 1 node instance.

This tutorial is really useful. It's good to run through it on paper a few times. In particular you seem to be missing steps 4,5 and 6

Programming / Re: Ambushes
« on: October 06, 2012, 01:14:22 AM »
Interesting post. I think the filtering method you suggest is nice and would also be useful for many other purposes where certain map fragment patterns would be useful to find (eg for placing traps, detecting corners of rooms, etc).

One question I have is how do you know which direction the player will come from? I suppose you can guess and tolerate the ambushers screwing up occasionally and being caught out by the player, but did you have something more clever in mind?

Programming / Re: Strange input issue! (
« on: October 03, 2012, 04:54:33 PM »
I've never used VB.Net but I did use VB6 and I vaguely recall you could use the Or keyword for both logical or bitwise or and the compiler decided which based on context.

I don't know if it's the same with VB.Net, but in this case it does look like the Or operator in a case statement is bitwise. There's another operator OrElse for logical or.

So the line:
Case ConsoleKey.NumPad8 Or 38 Or 104

is basically getting resolved as
Case 110

because 38 bitwise or 104 is 110:

  100110  =   38
1101000  = 104
----------------------- OR
1101110  = 110

So the case block would have never hit because 110 was never coming through (110 is ConsoleKey.BrowserBack)

Perhaps OrElse would have worked, although I don't know if VB.Net allows logical or in case statements, I don't think c# does.

Case ConsoleKey.NumPad8 OrElse 38 OrElse 104

As for why it didn't work originally, I don't know but I would guess that with numlock on Console.ReadKey() returns ConsoleKey.NumPad0 thru NumPad9 for those keys but with numlock off it returns ConsoleKey.D0 thru D9 (or perhaps the otherway round)

Traditional Roguelikes (Turn Based) / Re: Infra Arcana (now at v13.1)
« on: September 27, 2012, 04:15:53 PM »
A new release of IA. That's the weekend gone then :D

Pages: 1 2 [3] 4 5 6