Real Time Strategy... again
Community Forums/Showcase/Real Time Strategy... again
| ||
| Its been about 6 months and I’ve been hard at work with real life. I have been thinking about a real time strategy game… again, so I dug up some of the previous versions that I’ve worked on in Blitzmax and started working on it again. I had a pretty decent start with a map editor, animated sprite, tiles, map, clickable pathfinding and some other stuff but I felt I needed to simply it a little more and just concentrate on the mechanics of the game. I got rid of the animated sprite and decided just to use colored circles, triangles and squares to represent the units for now. One of the things I needed to do is make it when the user selects a unit and clicks on a tree, the unit needs to move to the closest walkable tile adjacent to the tree. This got a bit tricky and I had to look up methods of finding distance between 2 tiles. I found a java tutorial that led me to the Pythagorean Theorem which worked like a champ. Of course it leads the unit to the closest adjacent tile, but does not use the shortest path to get to the tree. It will work for now.  Another subject I worked on was being able to add a castle when the user clicks on a “Peasant” unit. I had to add a clickable castle button and when the user clicks it, it will allow them to place a castle on the map. The castle turns red if it cant be placed on that tile or green if can.   Now I will be working on some of the following areas… - Not allow placement of buildings in occupied tiles (by units) - When user clicks a tree, unit will gather wood and return it to the castle - When user clicks a stone, unit will gather stone and return it to the castle - Allow user to build farm, unit will gather food and return it to the castle - create gold mines and allow units to gather gold Of course with real life, this can definitely be a long time coming! :) Hopefully I will keep up with updating the blog as work progresses! You can visit the blog at http://yellzbellz.com/wordpress/ Thanks! Last edited 2012 Last edited 2012 |
| ||
| Look up A-Star (A*) pathfinding. Also, if you make the diagonal move a little more costly then the left/right/up/down, then the path wouldn't have that little jont into the woods. |
| ||
| Thanks for the input. I'm not really understanding what your saying with "Look up A-Star pathfinding". Thats what I'm using here. The jont in the woods can't be fixed by upping the diagonal cost. Right now I'm using 10 for Horizontal movement and 14 for diagonal. The problem with the jont is that the cell the unit goes to is 3 squares away from target, where as the cell above it is 4 squares away from target. This makes the jont cell a better pick as far as the fVal (gval + hval) goes. The proper way of fixing this would be to follow true A-Star pathfinding and not skip over the part that says... "If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything. On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below." http://www.policyalmanac.org/games/aStarTutorial.htm Of course I've never figured out a good algorithm for handeling this scenario, so for now, you'll see a little jont in my games. :) I did try your advice though just to see what would happen. I had to change the diagonal cost to 20 for the path to change. It changed a bit too drastic and cost a lot more time to find paths. Using 10/14 costs, it took 461ms to go from upper left corner to bottom right corner. With 10/20 costs, it took 4339ms. Thanks for the advice though, I always appreciate input! |
| ||
| Hi Xyle, glad to know you were able to score some time for gamedev. Here's something I've seen on a Valve article on 3D artificial intelligence, but the method is so brilliant that it might work for your 2D scenario: each time the player reaches a node, compute the visibility the player has of each future node he's going to walk through. If the player can 'see' any of these future nodes (without any unwalkable tiles blocking vision), he can also go directly to those nodes, so you can discard a lot of redundant path nodes inbetween with this, making your paths more efficient and realistic. So instead of the "compute A* path, move through computed path" cookie-cutter, try this: • Using visibility to clear a path of redundant nodes:  1) Compute A* path as usual. 2) Set the character to move through the path.  3) Each time the character arrives at a new node, compute the visibility this character has of each remaining node in his path. The node that's most advanced down the path AND is visible to the character at the same time is the 'best next node' to head to - you can clear all other nodes between the current one and this 'best next node', as they're all redundant.  4) All tiles that were intersected by the line of sight that tested for that 'best next node' are now the new nodes of the short path you will use to reach the 'best next node'. 5) Go back to #2. Hope that makes sense. You'll probably need to spend a few hours coming up with the logic involved to check a chain of tiles between two other tiles (the character's and the current node being tested for visibility's). Line-plotting algorithms come to mind. It's all quite fast in the end - even with multiple characters - so don't worry about performance. |
| ||
| Thats a really good idea and definitely worth looking into. I appreciate the tip. I've never seen this approach when working on pathfinding. I'll dive into it and take a look at the better path method also. Thanks! |
| ||
| Your A* function came up with that path because it wanted to use grass tiles right? Because they cost less to go over. This visibility technique looks more natural though. Actually there is no need for this technique if you simply tell the A* to ignore the cost of different terrains. It will come up with the same path as the visibility function. |
| ||
| I agree with slenkar. Unless the grass movement cost is lower, there is no reason that A* would have taken that path if diagonal moves are more costly. |
| ||
| This guy has some great explanations of coding A* pathfinding, among other things. http://www-cs-students.stanford.edu/~amitp/gameprog.html |
| ||
| I agree; when an A* is properly tuned\implemented it should give the same 'efficient path' every time, as if the character is able to see distant nodes. If it's possible to rework the A* to avoid having to use any aid such as the visibility test, it's better! EDIT: Just ocurred to me; the visibility test is best used for non-uniform node maps like navmeshes, polygonal maps etc. - asymmetrical arrangements of nodes where the character can roam freely and not necessarily in a grid-like manner. These maps are always 2D (even in 3D games), as the nodes are arranged on the X~Z plane. Last edited 2012 |
| ||
| Great feedback! Thanks for all the input. Different kinds of terrain do not have any weight in movement costs. Using the method described in the article linked above, where you see if a cell is already in the open list and if so, see if the cell is better reached from that cell would solve this issue.  In the picture, with the "jont" path where it is going through 106 to reach 85... Cell: 85, gVal: 94, hVal: 30, fVal: 124, parent:106 Cell: 86, gVal: 76, hVal: 40, fVal: 116, parent:87 Cell: 87, gVal: 66, hVal: 50, fVal: 116, parent:88 Cell: 106, gVal: 80, hVal: 30, fVal: 110, parent:87 If the path were to go through cell 86 to reach 85 instead... Cell: 85, gVal: 86, hVal: 30, fVal: 116, parent:106 Cell: 86, gVal: 76, hVal: 40, fVal: 116, parent:87 Cell: 87, gVal: 66, hVal: 50, fVal: 116, parent:88 Cell: 106, gVal: 80, hVal: 30, fVal: 110, parent:87 So if the path were to go through cell 86 to reach 85, cell 85 would have lower values then it does when the path goes through cell 106 to get to 85 and would definitely be a better route. I just have to add code to make the pathfinding routine do this just like the article says to do. :) I will take a gander on this, hopefully in the near future. Thanks! Also Taskmaster - That is another great site for Pathfinding, amoung other topics. Thanks! Last edited 2012 |
   |