Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

936 Good

About Makers_F

  • Rank
  1. 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. 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. Makers_F

    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. Makers_F

    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?
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!