# Makers_F

Member

26

936 Good

• Rank
Member
1. ## Procedural Generation of Puzzle Game Levels

The complexity is based on the total number of nodes that you look at, not at the depth (the number of moves). With depth = 0 (no move), you will look at 1 node (the initial state). If you have 2 moves possible, at depth = 1 you'll look at 2 nodes, at level 2 at 4.. At level 30, you will look at 2^30 nodes. You know how many nodes you will look at, if you check with max level 0, then max level 1, ... , then max level 29? Let's see: solution So, if you check FROM level 0 TO level 29, you are actually analysing less nodes that just looking at level 30 (exactly 1 node less). If you have 4 moves, it gets waay worse. With your method, you are actually looking at level 30, then level 29, and down that way until you don't find a solution, which might be at something like level 10. This has a complexity that saying it's terrible is a great compliment. Your method would probably fail for grids really little bigger than the current one. With the one I told you, you would get a way faster solution if there is one in less than 30 moves, and if there isn't one, it would take a slightly more than your current one. So, you have two options: you either implement UC, or you implement interative deepening like I described it. Space state explorations is a kind of problems studied a lot and with precise optimal approaches, I highly suggest you to follow them, unless you want your algorithm not be able to tackle bigger problems (or just be slow with current ones ;) ) @apatriarca since he talks about a LIFO, I think he implemented a depth first search, so it's not guaranteed to be optimal. On this aspect he was right ;)
2. ## Procedural Generation of Puzzle Game Levels

Can you tell us a bit about your background? Anyway, there are a couple of theorical problems in your post 1) The correct search strategy you are looking for is Uniform Cost. It is obrained by using a priority queue sorted on the number of moves to reach the state, instead of using your LIFO (which behaves like a depth first) 1.1) Right now you are making a strange combination of Iterative Deepening strategy. That's pretty bad as complexity. If you don't want to change to uniform cost, you should probably implement a correct iterative deepening. (so you start with a max moves of 1, and then proceed to increase it every time it fails to find a solution. When it stops you find the optimal solution) Still have to read it thoroughly, but I noticed these at a first read
3. ## Grounded Pointers

After reading this article I installed static code analysis plugins for my personal projects. I already used sonar for my thesis project, but didn't bother to set any S.C.A.T. up for my personal projects. Even if I (surprisingly) had just 2 minor warning, definitely the situation in programming is getting better
4. ## How To Publish on GameDev.net

I read the article and made a search on the forum, but i didn't find any information about how to peer review. I'm interested in it, should i sign my name somewhere to get the approval?