 |
| Nobody ever said getting shot by Cupid was an enjoyable experience... |
Saturday, September 10, 2011
Thursday, September 8, 2011
One step forward, Two steps back.
Today is a sad day, my friends. After wrestling with a problem in my pathfinding code I have come to a conclusion:
I know where the problem is, but I have no clue how to fix it.
Well, that's not entirely true, that's just the more dramatic and depressing way to say it, which I'll go with for now.
That's on top of starting school again too. So much programming ahead of me... and that doesn't even include my own projects I want to do. I hope I don't become a shut-in this quarter for all the programming required of me.
Anyway, the problem with my pathfinding, if any of you care (raise your hands.... oh... nobody?) actually had to do with my "genius" implementation of influence modifiers. If you remember from a few posts back, influence modifying is adding on points to the scores of individual nodes, to make them more costly to go through, effectively marking the node as a "no-no" during a path search.
On it's own, this practice is perfectly fine, but I, in my infinite wisdom (sarcasm) used influence modifiers to try and keep ships from crashing into each other. A ship would spawn, and then it would mark it's path with artificially high costs. Not a problem, initially. When a whole bunch of little ships start spawning however, and they are all going to generally the same spot, the most-efficient-path method of A* gets really screwed up if all of the best path's are marked with artificially high costs, and it ends up spitting back a failed path search.
Now in some implementations of A* it will just end up searching EVERY SINGLE NODE in an effort to find a route, but mine doesn't go that far. I'm not entirely sure if this means that the pathfinding method I implemented isn't A* still because it doesn't but the fact of the matter is I'm going to have to make some fundamental changes to the system yet again because I didn't used my head earlier on in the process.
Seeing a trend here, are we? Me too. Hopefully I learn to think before I code.
Anyway, this doesn't necessarily mean I need to change how I operate my influence modifications, but... yes. I realize now I can't just add on scores to the score designed to find the fastest route. If all the nodes around the end node have too high of artificial scores, then the end node won't be found. I either adjust the implementation, or re-work how the influence scores actually influence or I adjust my A* algorithm to search every last node to find the target. Which would end up just taking the system longer and in the end would be lazy programming on my part, and I would probably end up learning less from it.
...Like I'm learning anything at all from all of this?
So... I'm stuck re-working my pathfinding probably for the next few days.
On the bright side... wait, there is no bright side. Not that I can see initially, anyway. I've got class starting, they won't be easy. Lots of programming ahead, and like I said, my game work will all be on my own costly time now.
My academic adviser, possibly one of the most awesome professors on the planet, much less the North American continent, has given me a position grading for him, as well as a position as a lab moderator. And Sensei wants me to try to ready up for the next tournament. These things can be taken in a negative light, more work and more Judo, but work equates to food, and I love Judo, as well as the physical activity that I'm desperately going to need after sitting around on my fat butt all day.
And so it beings.
Hopefully the next update finds me in a better mood.
Until then, denizens of the world wide tangled mess of interwebs,
-Kev
I know where the problem is, but I have no clue how to fix it.
Well, that's not entirely true, that's just the more dramatic and depressing way to say it, which I'll go with for now.
 |
| Exactly how I feel right now |
Anyway, the problem with my pathfinding, if any of you care (raise your hands.... oh... nobody?) actually had to do with my "genius" implementation of influence modifiers. If you remember from a few posts back, influence modifying is adding on points to the scores of individual nodes, to make them more costly to go through, effectively marking the node as a "no-no" during a path search.
 |
| YOU SHALL NOT PASS! |
On it's own, this practice is perfectly fine, but I, in my infinite wisdom (sarcasm) used influence modifiers to try and keep ships from crashing into each other. A ship would spawn, and then it would mark it's path with artificially high costs. Not a problem, initially. When a whole bunch of little ships start spawning however, and they are all going to generally the same spot, the most-efficient-path method of A* gets really screwed up if all of the best path's are marked with artificially high costs, and it ends up spitting back a failed path search.
Now in some implementations of A* it will just end up searching EVERY SINGLE NODE in an effort to find a route, but mine doesn't go that far. I'm not entirely sure if this means that the pathfinding method I implemented isn't A* still because it doesn't but the fact of the matter is I'm going to have to make some fundamental changes to the system yet again because I didn't used my head earlier on in the process.
 |
| This is me. Yes, my nose is that big. |
Anyway, this doesn't necessarily mean I need to change how I operate my influence modifications, but... yes. I realize now I can't just add on scores to the score designed to find the fastest route. If all the nodes around the end node have too high of artificial scores, then the end node won't be found. I either adjust the implementation, or re-work how the influence scores actually influence or I adjust my A* algorithm to search every last node to find the target. Which would end up just taking the system longer and in the end would be lazy programming on my part, and I would probably end up learning less from it.
...Like I'm learning anything at all from all of this?
 |
| Yeah I'm with Stupid here. I also have Schizophrenia. ...wait... crap. |
 | |
| You know it. |
My academic adviser, possibly one of the most awesome professors on the planet, much less the North American continent, has given me a position grading for him, as well as a position as a lab moderator. And Sensei wants me to try to ready up for the next tournament. These things can be taken in a negative light, more work and more Judo, but work equates to food, and I love Judo, as well as the physical activity that I'm desperately going to need after sitting around on my fat butt all day.
And so it beings.
 |
| I think it's a zombie. Who knows. |
 |
| WHAAAAAAAAAAAAAAAT?! |
 |
| See? Not everything I draw is repulsive... I hope. |
Hopefully the next update finds me in a better mood.
Until then, denizens of the world wide tangled mess of interwebs,
-Kev
Saturday, September 3, 2011
Friday, September 2, 2011
Tuesday, August 30, 2011
Every Day I'm Doodle-in'
 |
| Why I haven't asked her out. |
 |
| Gulp. |
 |
| Welcome. I'm Steve, and I'll be your Orientation Leader. |
-Kev
Monday, August 29, 2011
Making my little ones not-stupid.
If there's one thing a game designer and programmer should avoid at most costs it is getting too attached to you designs or creations.
Now this is not a rule, as sometimes it's required that you become attached to what you make, and becoming attached makes it better, as in terms of story lines or characters and sometimes in terms of game play features that you just know are going to take off.
But there are also times where what you have been working on, your baby, your great idea, clearly isn't working how it was supposed to you, and you have to choke back the tears and put ol' Yeller down.
For me I get very attached to my AI (Artificial Intelligence, which is a very loose term at this point, because I wouldn't consider anything I've created to be actually intelligent) and I feel as close to a father as a single 19 year old male can feel. A father with high standards, but they are my creations none the less, and I want them to succeed and prove themselves to the outside world.
Unfortunately their success is dependent upon my skills as a logic-thinking and programmer. For reference, that's like trying to teach your own kids how to sky dive or hang glide from a book because you know best. Unless you have a lot of kids at your disposal, have somebody who's experienced teach them. I don't have the luxury of doing that, however.
So what have I done, anyway, in my week off? AI coding, of course. From a very informative article, that can be found here, I first built a structure and system for pathfinding. I wish I had the ingenuity to have developed my own method for pathfinding, but as is A* pathfidning is pretty tried-and-true stuff for games (at least 2D games, elements of A* can be used for 3D games too, but there are notable differences)
If you stomached the article I provided, you can kind of ditch this next paragraph, if not, I'll explain A* (A-star) pathfinding to you in as simple terms as I can. Using A* pathfinding a network of square nodes are set up. These nodes can be listed as walkable or unwalkable. To find a path to a destination, you take the beginning node and the ending node (path start and end) and from the first node you repeat the following:
Check each of the surrounding 8 nodes for the lowest "f" score. The "f" score of a node is determined by two other factors, a movement score of the node, and a heuristic score. Heuristic is a funny word, but it essentially means a process of finding the answer or solution for ones self (or trial-and-error, if you will)
The movement score is, at least for square nodes, either 10 or 14. Moving diagonally will result of a score of 14, and moving straight up-down or left-right has a score of 10. The scores depend on the surrounding nodes location next to the starting node. Why 10 and 14? It is essentially a distance cost. Between a node directly to the left of our starting node, the "distance" between the nodes is one. but a node to the left and down one from the starting node is at a diagonal, the "distance" between the two nodes, using some simple math, would be about 1.4 (that's factoring in considerable rounding)
Using whole numbers is easier on a computer that floating point numbers such as 1.4, so we use 10 and 14. The Heuristic number can be determined by any number of methods, but I used the method suggested in the article, or the Manhattan method, which simply takes the number of nodes to get to our destination both horizontally and vertically, and then multiplies that number by 10.
Still with me?
Okay, so how does all of that help? Essentially, by following the nodes with the lowest combination of movement and heuristic scores, you will end up at the target node. It's not quite that simple, but for the sake of my story we shall assume it is.
So, using pathfinding my little minions can find there way from where they spawn, to where there target is without running into - or through - any walls.
Whew!
Oh wait, there's more.
So, what do you do when you have multiple little minions spawning and you don't want them to run into each other?
There is no simple solution to this fix, and as of now my little guys still run into each other sometimes. But I have used a method known as influence mapping to keep them from doing it too often.
Oh no, what's influence mapping? It runs on top of the node network I set up for pathfinding. Nodes are given a third score to be added to the movement cost and heuristic score. names vary, and there could actually be a number of different score-modifiers involved, but for the current purpose of my game, there's one score, simply called a cost modifier that works on "networks" (teams, essentially. Each team has it's own network on the node map with different cost modifiers, instead of using two different node maps) Influence mapping does exactly what it claims to do, it influences the path that the minions are trying to find. if several minions went through a choke point and subsequently died, do I want my other minions to go through that same point and die? No, no I do not. So how do I prevent them from doing this? Add artificially high scores to the nodes through the choke point, so that a route through the choke point becomes far more "expensive" than a route around the walls somewhere. That way, the minions can "talk" to each other. This here, this is a bad path. That there, that is a good path. (simply create a negative cost modifier, and suddenly certain nodes become excellent routes to travel through)
Soooooo... back to my point, if, when a minion creates a path, he adds to the cost modifier at each node along his path, it makes another minion less likely to use the same path as the first, preventing a good number of accidental collisions.
I now feel like a proud father, my minions are moving and finding good paths all on their own, and for the most part aren't doing stupid things like colliding with one another on a frequent basis.
I'm so proud! Now my goal is to make them even smarter, and for them not to run into each other like suidice pilots when they attack each other.
Quick, to the programming-cave!
-Kev
Now this is not a rule, as sometimes it's required that you become attached to what you make, and becoming attached makes it better, as in terms of story lines or characters and sometimes in terms of game play features that you just know are going to take off.
But there are also times where what you have been working on, your baby, your great idea, clearly isn't working how it was supposed to you, and you have to choke back the tears and put ol' Yeller down.
For me I get very attached to my AI (Artificial Intelligence, which is a very loose term at this point, because I wouldn't consider anything I've created to be actually intelligent) and I feel as close to a father as a single 19 year old male can feel. A father with high standards, but they are my creations none the less, and I want them to succeed and prove themselves to the outside world.
Unfortunately their success is dependent upon my skills as a logic-thinking and programmer. For reference, that's like trying to teach your own kids how to sky dive or hang glide from a book because you know best. Unless you have a lot of kids at your disposal, have somebody who's experienced teach them. I don't have the luxury of doing that, however.
So what have I done, anyway, in my week off? AI coding, of course. From a very informative article, that can be found here, I first built a structure and system for pathfinding. I wish I had the ingenuity to have developed my own method for pathfinding, but as is A* pathfidning is pretty tried-and-true stuff for games (at least 2D games, elements of A* can be used for 3D games too, but there are notable differences)
If you stomached the article I provided, you can kind of ditch this next paragraph, if not, I'll explain A* (A-star) pathfinding to you in as simple terms as I can. Using A* pathfinding a network of square nodes are set up. These nodes can be listed as walkable or unwalkable. To find a path to a destination, you take the beginning node and the ending node (path start and end) and from the first node you repeat the following:
Check each of the surrounding 8 nodes for the lowest "f" score. The "f" score of a node is determined by two other factors, a movement score of the node, and a heuristic score. Heuristic is a funny word, but it essentially means a process of finding the answer or solution for ones self (or trial-and-error, if you will)
The movement score is, at least for square nodes, either 10 or 14. Moving diagonally will result of a score of 14, and moving straight up-down or left-right has a score of 10. The scores depend on the surrounding nodes location next to the starting node. Why 10 and 14? It is essentially a distance cost. Between a node directly to the left of our starting node, the "distance" between the nodes is one. but a node to the left and down one from the starting node is at a diagonal, the "distance" between the two nodes, using some simple math, would be about 1.4 (that's factoring in considerable rounding)
Using whole numbers is easier on a computer that floating point numbers such as 1.4, so we use 10 and 14. The Heuristic number can be determined by any number of methods, but I used the method suggested in the article, or the Manhattan method, which simply takes the number of nodes to get to our destination both horizontally and vertically, and then multiplies that number by 10.
Still with me?
Okay, so how does all of that help? Essentially, by following the nodes with the lowest combination of movement and heuristic scores, you will end up at the target node. It's not quite that simple, but for the sake of my story we shall assume it is.
So, using pathfinding my little minions can find there way from where they spawn, to where there target is without running into - or through - any walls.
Whew!
Oh wait, there's more.
So, what do you do when you have multiple little minions spawning and you don't want them to run into each other?
There is no simple solution to this fix, and as of now my little guys still run into each other sometimes. But I have used a method known as influence mapping to keep them from doing it too often.
Oh no, what's influence mapping? It runs on top of the node network I set up for pathfinding. Nodes are given a third score to be added to the movement cost and heuristic score. names vary, and there could actually be a number of different score-modifiers involved, but for the current purpose of my game, there's one score, simply called a cost modifier that works on "networks" (teams, essentially. Each team has it's own network on the node map with different cost modifiers, instead of using two different node maps) Influence mapping does exactly what it claims to do, it influences the path that the minions are trying to find. if several minions went through a choke point and subsequently died, do I want my other minions to go through that same point and die? No, no I do not. So how do I prevent them from doing this? Add artificially high scores to the nodes through the choke point, so that a route through the choke point becomes far more "expensive" than a route around the walls somewhere. That way, the minions can "talk" to each other. This here, this is a bad path. That there, that is a good path. (simply create a negative cost modifier, and suddenly certain nodes become excellent routes to travel through)
Soooooo... back to my point, if, when a minion creates a path, he adds to the cost modifier at each node along his path, it makes another minion less likely to use the same path as the first, preventing a good number of accidental collisions.
I now feel like a proud father, my minions are moving and finding good paths all on their own, and for the most part aren't doing stupid things like colliding with one another on a frequent basis.
I'm so proud! Now my goal is to make them even smarter, and for them not to run into each other like suidice pilots when they attack each other.
Quick, to the programming-cave!
-Kev
Subscribe to:
Posts (Atom)