sponsors gamedev.net search:

Dynamic Worlds One of the biggest problems people emailed me about after the last article was 'how do I deal with a network which changes?' For example, say a ceiling collapses somewhere, removing one of the paths between two nodes. How do we deal with that, without recalculating the entire network? I think I have a solution now (oddly enough, penned while sitting around at a game development studio, waiting for an interview), so here you go, boys and girls. We're only going to deal with a situation where one path has been removed. We can't escape recalculation altogether in a properly dynamic network - there's no way of knowing which paths would disappear/reappear and when - so we want to minimise the number of nodes we process. The technique uses a sort of 'ripple propagation.' As we move further away from the affected path within the network, the number of nodes needing to be processed get fewer and fewer, until eventually the network doesn't change - like how a ripple dissipates as you get further from the point of impact. The algorithm is recursive/repetitive. For each node you feed in, you recalculate it, and compare the recalculated version to the original version. If there have been no changes, then obviously the node is not affected by the change in the network, so processing of this node stops. However, if there have been changes, then you process all nodes connected to the current node (that have not already been recalculated). Let's take our network from earlier, and remove the path BC: The original path table looked like this:   To A B C D E From A - B C C E B A - C C A C A B - D A D C C C - E E A A A D - We'll keep two lists - a 'nodes to be processed' (tbP) list and a 'nodes already processed' (aP) list. To begin with, the tbP list is 'BC' and the aP list is empty. We process the first node on the tbP list - B. Using visual inspection again, we rebuild the row in the table. In fact, in this case, we can see that B only has one path left, so all its values will have to use that path. So, the original row was: From B A - C C A And the newly calculated row is: From B A - A A A We can see that the row has changed. So, we get all the nodes which were connected to B - that is, assuming the connection BC still exists - and see if we need to process them. The list of nodes connected to B is AC. Node A does not appear in either the tbP or aP lists so we add it to the tbP list. Node C is in the tbP list already, so we leave it alone. That's node B done, so we move it from the tbP list to the aP list, and move to the next node in the tbP list. The tbP list is now 'CA' and the aP list is now 'B.' The current node is now C. The original row for C was: From C A B - D A The newly calculated row is: From C A A - D A It's only a small change, but it's a change. So, we get our list of nodes that used to be connected to C - 'ABD' - and work out which ones need adding to lists. A is already in the tbP list; B is in the aP list; but D is in neither, so we add it to the tbP list. Finally, we move C to the aP list. The tbP list is now 'AD' and the aP list is now 'BC.' The current node is now A. The original row for A was: From A - B C C E The new row for A is: From A - B C C E No change this time. So, we can move A to the aP list and continue processing the tbP list, without adding any more nodes. The tbP list is now 'D' and the aP list is now 'BCA.' The current node is now D. Original row for D: From D C C C - E New row for D: From D C C C - E Again, no change, so we move D across to the aP list. Now, the aP list is 'BCAD,' but the tbP list is empty - which means we've finished. The new path table is:   To A B C D E From A - B C C E B A - A A A C A A - D A D C C C - E E A A A D - Notice that we didn't even need to process node E with this method. The path from node E to node B hasn't changed (EAB), but it could quite easily have done. The two lists can, in fact, be combined - you could just use one list and keep a 'cursor' in it, rather than using the top node of the tbP list each time. The method can be used for both adding paths and removing paths - you just ensure you start with the correct nodes in the tbP list. As for adding/removing nodes, nodes are only significant in the network when they have connections. A node with no connections might just as well not exist. So, when removing a node, simply remove all of its connections (using the method described here), and when adding a node, simply change the network and propagate the change (again, using this method). The only thing you need to watch out for when adding a node is that the path table will have to be expanded to have room for the new node's routes. Often, you'll have a situation where more than one path has to be added/removed. You could simply add/remove each path in turn; however, that would result in having to recalculate some nodes several times, rather than just the once that a single path would require. So, you can actually do as many paths as you want at once; you just make sure that all changes have been made before propagation begins, and that the tbP list contains all the endpoints of the affected routes. When adding routes AB and CD, you start with a tbP list of 'ABCD,' and so on. It's more efficient than propagating each path separately. Education

Contents   Introduction   Dynamic Worlds   Education   Echoes of the Past   Printable version   Discuss this article