• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Tom Atom

Members
  • Content count

    8
  • Joined

  • Last visited

Community Reputation

288 Neutral

About Tom Atom

  • Rank
    Newbie
  1. Hi,    a few days ago I finished my first book. Theme is creating procedural endless runner in Phaser engine. Although, language used in book is TypeScript, it is easy for JavaScript developers to follow. Book, as well as list of chapters, is available at Gumroad. Short post with additional details is on my blog.   [attachment=33496:Book_new.jpg]  Reader of the book will build full game from start to finish. You can see and play it here.   [attachment=33497:GoblinRun02_small.png][attachment=33498:GoblinRun04_small.png]    Generator for game build in book is very flexible and can be reused or extended for other games. Goblin animations are skeletal - book will teach you how to play it in Phaser with Spriter Player for Phaser. Game is then polished with particle effects, sounds and music. Also chapter focused on handling various screen sizes is in place.
  2.    Yes, I understand this. This is reason why I added the rules described in article (a,b,c,d rules in part Solver) to terminate some searches...    I compared Uniform Cost search as described here at wiki: http://en.wikipedia.org/wiki/Uniform-cost_search with my algorithm and found that I was missing only last thing: I was using stack which did not prefer nodes with lowest cost. All I had to do was only to replace it with priority queue as you mentioned in your original post (implementation is in Java, so I replaced Stack with PriorityQueue + Comparator).    It works like charm now and I do not have to iterate from level 30 down, but I can search like apatriarca suggested in his post from 1 until I find the solution. I tested on several levels where previously a few iterations were needed to reach the shortest solution and now the shortest solution was found as the first one.    So, thanks for your help!
  3. If you ever wanted to create a puzzle game you probably found that implementation and coding of game rules is relatively easy, while creating the levels is a hard and long-lasting job. Even worse, maybe you spent a lot of time on creating some levels, with intent to incorporate specific challenges into it, but when you asked your friend to try it, she solved it in a totally different way or with shortcuts you never imagined before. How great would it be if you found a way to employ your computer, saved lot of time and solved issues similar to the above mentioned... Here is where the procedural generation comes to the rescue! It is necessary to say that while there is only one correct way how, for example, to sum vectors and every programmer wanting to do it has to follow the same rules, when it comes to procedural generation you are absolutely free. No way is right or bad. The result is what counts. Fruit Dating - its rules and features In past days we released our Fruit Dating game for iOS devices (it is also available for Android and even for unreleased Tizen). The game is a puzzle game with simple rules. Your target is to match pairs of fruit of the same color simply by swiping with your finger. The finger motion matches the tilting of the board in any given direction. So, while trying to fulfill your goal, various obstacles like stones, cars or other fruit, get in the way. Simply, all movable objects move in the same direction at once. To illustrate, in the pictures below you can see first level that needs 3 moves to match a pair. [table] [tr] [td] [/td] [td] [/td] [/tr] [tr] [td] [/td] [td] [/td] [/tr] [/table] Over time new features are introduced: [table] [tr] [td][/td] [td] One-ways are placed on the border of the tile and limits directions in which you can move.[/td] [/tr] [tr] [td][/td] [td] Anteaters can look in any direction, but its direction is fixed and unchanging during the level. When fruit is in the direction of the anteater and no obstacles are in the way, the anteater will shoot its tongue and drag the fruit to it.[/td] [/tr] [tr] [td][/td] [td] Mud can be passed through with stones, cars or barrels but not by fruit. When the fruit falls into mud it gets dirty and there is no date![/td] [/tr] [tr] [td][/td] [td] Sleeping hedgehog is sitting on a tile and wakes up when hit by something. If hit by a barrel, stone or car he falls asleep again as these items are not edible. But when he is hit by fruit he eats it.[/td] [/tr] [/table] You probably noticed that the game is tile-based which simplifies things as each level can be represented with a small grid. Maximum size is 8x8 tiles but as there is always solid board, the "usable" area is 6x6 tiles. It may seem to be too small but it proved that some very complex puzzles can be generated for it. With the basic rules (as the additional features were added later) I started to build my generator. My first thought was that someone in the world surely already solved a similar problem, so I started to search the internet for procedural generation of levels for puzzle game. It showed that this topic is not widely covered. I found only a few articles useful for me. Most of them were about generating / solving Sokoban levels - for example: http://larc.unt.edu/ian/pubs/GAMEON-NA_METH_03.pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=52E99748D5C48013A84BA983612AB7C4?doi=10.1.1.47.2303&rep=rep1&type=pdf It was also interesting, that most of them were written by academic people (professors of Sokoban! :-)) From the papers I learned two things: first, when generating something randomly it is good if it has some symmetry in it as people will perceive it more positively. Second, the algorithm is up to you, but none is ideal. Solver As it was obvious that every generated level will have to be tested (whether it is possible to solve it and how easy or hard it is) I first wanted to code a solver. As at that time I was only considering basic rules and not features added later I came up with these ideas for the solver: a) from initial position you can start in any direction (up, left, right, down), b) from next position you can continue in any direction again, c) in any position check for fruit match, remove matched fruits from board and continue with b) until some fruits remain on board. As you can see, it is a simple brute force approach. So, the number of possible board situations was: 4, 4*4 = 4^2, 4*4*4 = 4^3, ... 4^n. In the 10th move it was more than a million board situations and in the 25th move it was 1125899906842624 board situations. Okay, you could limit maximum moves to some number, let's say 10 and not be interested in more difficult levels, but there is hidden another danger. Some of the puzzles can be designed or generated in such a way that if a player does some bad moves in the beginning, she cannot finish the level. Or, in some levels you can get into a loop of board situations. If the algorithm branched early into such a way the level would be marked as not solvable, even if there were other branches with a simpler solution. Also if this algorithm found a solution there would not be any guarantee that it is the shortest solution - you would have to finish all branches to find the shortest solution. Beside this there are very often board situations in which one move in particular direction does not change anything. See third picture in "Fruit Dating - its rules and features" - there is no change if moved left. So, the rules changed: a) from current position try to move in any direction, b) if there is a change in the board situation, check if the situation is new or you already were in such a situation, c) if a new situation, store it along with solution depth (number of moves to get into this situation) d) if previously was in this situation and solution depth was equal or lower, terminate this branch. Else, remove old situation (as you just got into it with less moves) and continue. There are also other rules, like checking matches and thus terminating the whole process when a solution is found and later new rules when features were added, but this is the core of the solver. It quickly cuts whole branches without a solution. Beside solution depth, it also references to parent situations stored in each board situation, so it is easy to print the final solution in the end. Let's show it on the first level of the game: From the initial position a move into all four directions is possible. These are labeled 1-1, 1-2, 1-3, 1-4. The algorithm always tries to move right, up, left, down in this order. As it employs a stack to store situations to examine further, the first situation to continue is the last one pushed onto the stack (1-4 in this case). Again, first is a move to the right (2-1) and as this is a new situation it is put onto the stack. Next is a move up which results in situation 2-2. We already were in this situation and it was in the first round. So, we apply rule d) and terminate this branch - nothing is put onto the stack. Next, a move to left is tried. It results in a new situation (2-3) and this is put onto the stack. Last move is down, but there is no change between 1-4 and 2-4 so we put nothing onto the stack (rule b) ... no new situation = do nothing). Now, the stack top situation is 2-3. From it we move right and get into situation 3-1, which is equal to situation 2-1. But in 2-1 we were in the second round so we terminate this branch. Next we move up and fruits are on adjacent tiles, matched and as it was the only pair the game ends. The algorithm works, however it may not find the shortest way. It is simply the first solution found. To overcome this I first start with limiting the maximum moves to 30. If a solution is not found I say that the level has no solution. If a solution is found in, let's say, 15 moves I run the solver again with maximum moves depth 14 (15 - 1). If no solution is found then 15 was the shortest way. If solution is found in, let's say, 13 moves I run the solver again with 12 (13 - 1) maximum allowed depth. I repeat while some solution is still returned. The last returned solution is the shortest solution. Generator Now that the solver works, we can move to the generator and validate every generated puzzle with it. The generation phase can be split into two parts: generating walls generating on-board objects The wall generation always start with drawing a solid board border: Some random parameters are generated that say whether wall will be paint by one tile a time or two tiles a time. If two tiles a time then random symmetry is generated. It says where the second tile will be placed - if it will be flipped horizontally, vertically or rotated by 90 degrees or combination of these. First grid in the picture below is when one tile a time is painted. The rest are for two tiles a time with different random symmetries: The number of walls is random as well as their length and direction. Each wall starts from a random point on the border. Every wall is drawn in one or more iterations. After the first iteration, a random number between 0 and wall length - 1 is chosen. If equal to zero, the iteration loop is terminated. If greater than zero, then this number becomes the length of the next part of this wall. A random point on the current wall part is chosen, direction is set randomly to be orthogonal to the current wall part and the next part of the wall is drawn. The result may look like this (the numbers label the iterations): From picture it can be seen that every next part of the wall is shorter, so you can be sure it will be terminated at some point. So far all walls started from the border, so every single tile was always connected to the border. It looked boring so I added another step where inner walls are generated. Inner walls are not connected to any existing tile. It starts by selecting a random tile and checking if it is free as well as its 3x3 tiles surrounding. If yes a wall WILL be placed into the grid and the next tile is chosen based on random direction (this direction is randomly chosen before first tile was tested). Loop terminates when condition for 3x3 free surrounding is not true. Notice the stress on word "will" above. If you placed the wall into the grid immediately and proceeded to next tile, the 3x3 surrounding would never be free as you just placed a wall there. So I store all wall tiles into some temporary array and place them into the grid at once when the loop is terminated. During wall generation some of the walls may overlap others and it is very probable that some small spaces will be created or even that the initial area will be divided into several disconnected areas. This is something we do not want. And this is why in the next step I check which continuous area is largest and fill all others with walls. In this check I iterate through the whole board grid and if the tile is free I recursively fill whole continuous area with area ID (free tiles are tiles without wall and with no area ID yet). After that I iterate through the whole board again and count tiles for each area ID. Finally I iterate the board one last time filling all tiles with area ID with walls except for the area ID with the highest count. The whole process of generating walls can be seen in this animation. There is wall generation, inner wall generation and in the last frame a hole in lower right corner is filled during area consolidation: When walls are generated we can generate objects. We need at least one pair of fruit and zero or more obstacles (represented by stones, cars, barrels in the game). It would be nice if fruit was placed most of the times into corners, in the end of corridors or so. Placing it in the middle of an open area can be also interesting sometimes but the first is more preferable. To achieve this we will add weights to every free tile from the point of its attractiveness for placing fruit there. For the end of corridors, surrounded with tiles from 3 sides I selected weight 6 + Random(3). For tiles in horizontal or vertical corridors I selected weight 2. For corners I selected 3 + Random(3) and for free areas 1. From weights it is obvious that the most preferable placement is in the end of a corridor, followed with placement in corners, corridors and free areas. The random numbers in weights can also influence this and change weights between corridor ends and corners. The weights are generated only once for each generated level. Obstacles (stones, cars, barrels) are placed in a similar way, only the difference is these weights are separate from weights for fruits and also some random obstacles density, which says how many obstacles will be in level, is chosen. By the way, with the weights you can do other tricks. Features added later were sleeping hedgehog or anteater (see features description in the beginning). Placing them into the middle of a corridor made no sense so they have a weight for corridors = 0. In animation bellow you can see populating level with fruits and obstacles: The final generated level is in the static picture below. It takes 6 moves to solve it (right, up, left, down, right, up). Great, after 1-2 minutes of clicking on the Generate button we have a level that looks interesting, and the solution is possible in 6 steps (no one will play levels with solution in 30 steps!), while it is also not a breeze to find it. But ... it still could be little bit better. It is this point where our manual entries took place to make the levels nicer. 5. Editor The generation ended in the previous part. Our editor supports drag and drop, so it is easy to rearrange the objects to achieve a higher level of symmetry like this: It is important to re-test the level with the solver after adjustments. Sometimes a small change may lead to an unsolvable level. In this case the adjustments increased the number of solution steps from six to seven. With this manual step the approach to procedurally generated levels forks. If you need or want manual adjustment then procedural generation only works for you as a really big time saver. If this step is not necessary or you think that generated levels are OK then the generator can be part of the final game and players have the possibility to generate future levels by themselves. 6. Final result Generating levels procedurally saved us enormous amounts of time. Although the generator also generates rubbish - levels too easy to complete or levels too hard to complete, levels full of obstacles or ugly looking levels - it still saved us an enormous amount of time. It also allowed us to make selections and throw a lot of levels away. If we made it by hand it would take months. This is how levels generated in this article look like in the final game:
  4.   Thanks for feedback:    - my background: I am amateur programmer making simple games from my young years. Few months ago I changed to indie. When solving some problem I usually find some solution, but as I am often missing complex view, the solution may not be the best...,    - uniform cost searching: thanks for the point I will check it. It is funny that according to wikipedia I already used it in past in one of the games when doing A* path searching, but I did not know I was using uniform cost searching...,    - I am starting from other end because there is not any guarantee that level will have solution. If I started from 1 then I would have to step by +1 until maximum moves. If there was no solution I would run it 30 times. If I start from other end (max moves) I am sure there is solution or not after first run. Then I limit next run to found solution - 1 steps (to skip unnecessary runs). Maybe the best would be to check if there is solution with run with maximum moves (30)  and then do interval halving? It would skip more unnecessary runs I think.
  5. Hi,    I would like to introduce Shards - the brickbreaker. Shards is a modern and revolutionary approach to the classic brick breaking / Arkanoid game. Each level has its own fractal background, uniquely arranged as well as arbitrary scaled and rotated glass bricks for you to destroy. Enjoy various power-ups and a great original soundtrack.    Game is for Android, bada OS. iOS version is currently in approval process and Tizen version is lurking somewhere deeep in Tizenstore for its launch.   Features:  - each level has its own original stunning fractal background,  - glassy bricks are of arbitrary sizes and rotate to bring you interesting patterns to destroy,  - Shardiens - glassy enemies,  - ten power-ups will help you to clean the board,  - listen to an original soundtrack,  - play through three difficulty levels      On the project page here at Gamedev.net you can see detailed description as well as more screenshots: http://www.gamedev.net/page/indie/project.html/_/casual/shards-the-brickbreaker-r22   [sharedmedia=core:attachments:22768][sharedmedia=core:attachments:22770]  
  6. Shards is a modern and revolutionary approach to the classic brick breaking / Arkanoid game. Each level has its own fractal background, uniquely arranged as well as arbitrary scaled and rotated glass bricks for you to destroy. Game contains Shardiens - glassy enemies, 10 power-ups and great original soundtrack. [url=http://www.gamedev.net/page/indie/project.html/_/casual/shards-the-brickbreaker-r22]Click here to view the project[/url]
  7. FRUIT DATING is an original puzzle game in which you match pairs of fruit of the same color simply by swiping with your finger. While trying to fulfill your goal, various obstacles like stones, cars or other fruit, hinder the way. We added various other pitfalls such as: one-way tiles, puddles of mud or animal kingdom representatives looking forward to enliven their diet with juicy fruit! [url=http://www.gamedev.net/page/indie/project.html/_/casual/fruit-dating-r21]Click here to view the project[/url]
  8. [quote name='clb' timestamp='1350029832' post='4989390'] What is the bin packing algorithm you use? Just curious since I did research on that topic a few years back (results available on my website). [/quote] I read lot of articles but following 2 helped me a lot. Especially the first one which gives good idea but the implementtion is up to you: [url="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.200"]http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.200[/url] (click the pdf icon) [url="http://www.blackpawn.com/texts/lightmaps/"]http://www.blackpawn.com/texts/lightmaps/[/url] The resulting algorithm seems to be similar to what you have on your page - after placing any rectangle I am also tracking all possible new rectangles and for next sprite I am choosing the smallest one from these. I am starting with one big bin - tower of sprites with width of the widthest and changing (see the rules in linked file) step by step to one long row with hight of the highest sprite. There are also always severeal tries in each "bin" incorporating some chance in sorting the rects but generally the biggiest are placed as first.
  9. Hello, we started our blog at [url="http://sbcgamesdev.blogspot.com"]sbcgamesdev.blogspot.com[/url] First two articles describe free tool (SBC PicOpt) for creating sprite atlases we use in our games. It can not only create optimized atlas but it allows you also manage your custom properties for sprites (like collision boxes, etc.) It features also possibility to force POT export, include empty spaces between sprites or repeat top, bottom, left and right rim of the sprite which is very usefull to prevent artifacts in 2D openGL games. Also creating simple animations is possible. With tool you can easily create sheets like this with minimum effort: [img]http://2.bp.blogspot.com/-J1bxMHYnqGo/UG_r9ehBujI/AAAAAAAAABs/mTfW7GOS93c/s1600/SBCPicOpt_Tool_result2.png[/img] There is also description of format of output export files. Tomas