sponsors gamedev.net search:

Cheating Let's return to the scenario I originally presented you with, of the NPC entering a new environment. Rather than exploring, it uses a pre-calculated network to find the optimal route and reach its goal immediately, rather than having to explore. The matrix method that I've just demonstrated can be expanded for education. The mind is a little more complicated, but it's still understandable. Learning the path Another level: This one's a little more complex. The blue lines represent walls. We can build two extra tables from this that we'll need later. The first one is one that I will call our VIS table - it contains information about which nodes can 'see' which other nodes. Our bot will only 'learn' about the existence of a node when it 'sees' it. Sight Table - T: TRUE, BLANK: FALSE   To From   A B C D E F G H I J K L M N O P A - T                   T     T T B T -     T                   T T C     - T T                       D     T - T   T                   E   T T T -                       F           - T T T               G       T   T - T T               H           T T - T   T           I           T T T -               J                   - T T T     T K               T   T - T T       L T                 T T - T       M                   T T T - T     N                         T - T   O T T                       T - T P T T               T         T - (Yes, it is symmetrical along the To=From line - because we're working on the premise that if A can see B, B can see A. I can't think of a practical application where this isn't true, but if you can, kudos to you. :-) ) The second table we can build - a much smaller one - is a magnitude table. It lists the number of connections each node has. I won't do it yet, as we don't pre-build it, we build it as we go along. OK. Let's say that our bot starts at node A. He knows only node A, and nothing more. His route table looks like this:   To From   A A   Also, we can build the magnitude table I mentioned above: Node Magnitude A 0 Nice! B-) But, somehow, kinda useless. So, as our bot cannot move and has no higher priority goal (that is achievable - if he is hungry, for example, his limited network will not have any food in it), he decides to look around. Now, we are going to cheat a little here, but if we didn't, it'd look strange. Node A can see nodes B, L, O, and P. So, we pick the first of those, and turn the bot to face it. In actual fact, B, O, and P are all in a line. So, when the bot's field of view picks up node B, it will pick up nodes O and P as well. The first move is to add the newly discovered nodes to the route and magnitude tables, and to update the magnitude table:   To From   A B O P A -       B   -     O     -   P       - Node Magnitude A 1 B 2 O 1 P 2 Now, recalculate all new rows and columns in the route table:   To From   A B O P A - B B B B A - P O O P P - P P B B O - And that's it! There are a couple of extra things to mention. FirstLY, it's a good idea to keep a seperate, pre-calculated magnitude table for the entire network, so you can see when a node has been 'fully explored' (by comparing its value in the bot's magnitude table to that in the map's magnitude table). Exploration of the network is achieved by finding the nearest node that hasn't been 'fully explored' and looking at each of its links in turn to add them to the tables. Incidentally, see why I said we had to cheat? If we didn't use the VIS table to look at visible nodes in turn, rather than just rotating the bot's head and seeing what it could see, what would have happened at, say, corridor corners? The bot would have stopped, done a complete 360-degree scan, and then continued. A human player would just see that the corridor bends too the right, and continue. Of course, there could be access from above - which the bot would see, but the player would probably miss. Still, it's better than stopping at each node to perform a full scan. Secondly, what do you do when the addition of a node affects other routes? If, for example, node A was fully explored, then B, then P, the route from node L to node J would be LABPJ. However, if J was then fully explored, the route should become LKJ. How do you detect this? I haven't been able to find a nice, neat pattern that can be expressed with a single rule yet. Perhaps there isn't one. The best I can come up with is: After calculating values for the new cells, recalculate all rows for nodes directly connected to the new node, and then recalculate all rows for nodes with a magnitude of 3 or higher. So, with my previous example, after adding node K to the tables and calculating the values for column K and row K, you need to recalculate rows L and J, and then nodes B and P (which would each have magnitudes of 3, but would not have already been recalculated). Conclusion Right, that's all. This method has plenty of room for expansion - off the top of my head, assigning 'goodness' values to each node - for strategic importance, safety, proximity to health/weapons, etc - might be useful to break out of the loop situations I mentioned earlier. Oof. I'm going to go and eat some toast, I think. Questions, comments, etc, you can email me at rfine@lycos.com, post about this in the forums (I usually check) or catch me in #gamedev. Happy brainstorming! =]

Contents   Page 1   Page 2   Printable version   Discuss this article