 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Knowing the Path |
|
 |
Anonymous Poster |
|||
 Posted - 6/18/2002 7:27:56 AM |
||||
| just a small proof: given P: the shortest path between two nodes x and y with P1 = x, PI = Nodes on the Path and PN = y. Assumption: For any 1 < i < n, the path P1, P2, P3, ..., PI is the shortest Path from x to Node(PI). Proof: Lets assume, there exists a shorter path from x to Node(PI), called P'. Since P' is shorter than P, there exists at least one Node P'J that is not contained in P. Now P'J-1 is in P. From there, now exist two paths to PN (that is: y). The first path is of course P itself, the second path is the path containing the nodes of P1 to P'J-1 P'J to PI and PI + 1 to PN. This new Path from P1 to PN is shorter than P itself, which cannot be, since P is defined as shortest path between P1 and PN. Therefore, Dijkstra's algorithm is correct ;-)) |
||||
|
||||
 |
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 6/18/2002 9:11:03 AM |
||||
Thank you  I could see that it was correct, but couldn't write it as a mathematical proof... |
||||
|
||||
|
Guardian_Light Member since: 7/22/2000 From: Ontario, Canada |
|||
 Posted - 6/18/2002 9:39:46 AM |
||||
| Nice article, both interesting and got the throught process going in me. Hope to see more articles from you in the future. If all that matters is what you get in the end, why go through life? ~Michael Sikora |
||||
|
||||
 |
Gaiiden GDNet Content Lead Member since: 8/30/2000 From: Lincroft, NJ, United States |
|||
 Posted - 6/19/2002 1:01:22 AM |
||||
| Very nice read. Anything you can make into a table is good, very very good That's my fav thing about the whole idea. Definetly something I'll have to keep in mind, since I can't apply it to my current project. _________________________________________________________________ Drew Sikora A.K.A. Gaiiden ICQ #: 70449988 AOLIM: DarkPylat Blade Edge Software Staff Member, GDNet Public Relations, Game Institute 3-time Contributing author, Game Design Methods , Charles River Media (coming April/May 2002) Online column - Design Corner at Pixelate Unnoficial IGDA chat! [polaris.starchat.net -> #igda] NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum] |
||||
|
||||
|
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 6/19/2002 8:32:53 AM |
||||
| Thanks. Superpig - saving pigs from untimely fates - sleeps in a ham-mock at www.thebinaryrefinery.cjb.net |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 6/19/2002 2:33:16 PM |
||||
| Hi, very nice article ! i was wondering about a thing though: Is the magnitude table's only purpose to recalculate the nodes with a magnitude higher than 3 when new nodes are explored, in case a shorter path including that node comes up ? And why 3 btw ? |
||||
|
||||
|
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 6/19/2002 4:33:08 PM |
||||
| AP: that, and it's a quick way of seeing which nodes you have left to 'explore.' If your magnitude table value is less than the node's actual value, then there's a route there you haven't discovered. Why 3? I don't know. I just found that was the closest pattern. If anyone can find a definitive rule about which rows to recalculate, I'd like to hear it. It's probably 'anything with a magnitude greater than 1,' but there are several cases where the whole table doesn't need to be recalculated... If there's a network of 30 nodes - a small level - then by the time you're discovering the 20th node, you have to do 20! pathfinding calculations (20*19*18*17*16...) in a single frame, which can get a bit slow. A different method might be rather than recalculating the table, to 'mark' the values that need redoing as 'inaccurate information' so that they get recalculated as the NPC goes around a second time. Superpig - saving pigs from untimely fates - sleeps in a ham-mock at www.thebinaryrefinery.cjb.net |
||||
|
||||
|
jaxson Member since: 1/14/2000 From: Beaverton, USA |
|||
|
Posted - 6/20/2002 12:53:55 AM |
||||
| I may not completely understand your method as I'm afraid I only had time to do a quick read of the article. It was a very interesting approach. I do have one comment. Being able to travel from A to B does not always mean you can travel from B to A. If you take the case of a high ledge, for example, the bot could drop to the room below but might not be able to get back up without going 'the long way around'. It is possible I misinterpreted what you meant by visibility though, or missed where you discussed this point. In any case, just some food for thought. |
||||
|
||||
|
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 6/20/2002 2:15:16 AM |
||||
| jaxson: completely correct. I think I mentioned, this is for an undirected network. However, the principle still applies when working with a directed network (i.e., with one-way paths) - you just have to be a little more careful when calculating your routes. If there's no path to a node at all, then routes to it just get left blank. Could be interesting to investigate that situation, though... Superpig - saving pigs from untimely fates - sleeps in a ham-mock at www.thebinaryrefinery.cjb.net |
||||
|
||||
|
Mr Homm Member since: 7/1/2002 From: Hamburg, Germany |
|||
 Posted - 7/1/2002 5:44:00 PM |
||||
quote: |
||||
|
||||
|
Mr Homm Member since: 7/1/2002 From: Hamburg, Germany |
|||
|
Posted - 7/1/2002 6:43:01 PM |
||||
quote: OK, I think, I get this time :-). > Since P' is shorter than P, there exists at least one Node P'J that is not contained in P. I dont think so. Take a look at this situation: A-----C --B-----D One way to move from A to D is ACBD another is ABCD. Both ways have the same members of waypoints but have different lengths. Of course both are not the shortest ways from A to D. Try to look at the problem this way: If ABCD is the shortest way from A to D then ABC must be the shortst way from A to C, because if there where a shorter way from A to C (lets call it AEC) then AECD would be shorter than ABCD, because the way from C to D is equal in both cases. But that can't be, because ABCD is the sortest way. The problem of finding the best (shortest) way between two nodes in a graph is similar to the "Traveling Salesman" problem. One of the clasic problems of computer science. And as far as I know, there is no "easy" solution for this problem. The hard way is to calculate all n! possible combinations (n is the number of nodes). With n greater then 69 my pocket calculator resigns, because the result would have more than one hundert digits. At this point we are far away from something a computer could calculate between two frames. The idea of using tablets is good. Tables are like tined computing power; you need some time to make them, but once they are ready, you could use them at will. If the table consists of the shortest ways it would probably not reflect the knowledge of a NPC of the level. The NPC should only "know" what it sees, and not what's the best! From this point of view it's hard to use the optimal table for NPC movement, because the NPC would use information it does'nt know. One the other side it should not act like a idot. I think the problem is to find the amount of extra infomation a NPC should receive to act as a real opponent, and not be allmighty. [edited by - Mr Homm on July 1, 2002 6:48:52 PM] |
||||
|
||||
|
Cookie Monster Member since: 7/10/2002 |
|||
|
Posted - 7/11/2002 1:04:31 AM |
||||
| Nice article. I implemented something like that for the cold night bot (for kingpin) a while ago (ahhh, those foolish days...) First, I would like to mention an errata in the path table, from B to P, the next node would be P and not O. (Just in case people haven't realize it yet.) If I understood the algorithm correctly, all agents owns their own verseion of the table (else agents would magically learn from each other and would know about places they never been before.) These tables may become huge in practical cases. These look up tables reduces the path finding complexity to a single look up, but has, on the hand, a big memory complexity. It looks something like that: K*N*N, where K is the number of agents and N the number of nodes. I guess this may work for a small deathmatch environnements, where the maps are generally small and has a small geometry complexity, where agents only seeks and shoot, but in a richer environnement where agents may have to perform precise tasks, the node count increase to a level these tables eat all the memory available. Still, I think this technique could be very usefull combine with an A* map has a 2 level path finding. The path map is used to draw the "low res" draft of the path, and the A* map is used to dynamically compute the tiny details of the path (Am I clear?) Anyway, keep up the good work. Cookie Programmer, Insane Logics |
||||
|
||||
|
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 7/13/2002 9:46:53 PM |
||||
quote: Ah, yes. Can be pretty memory-heavy. As you say, best aimed at situations where there are a small number of nodes or agents. But assuming that it is small number of nodes, K*N*N is number of BYTEs. quote: Good idea. Using one node to describe each room, etc... Superpig - saving pigs from untimely fates - sleeps in a ham-mock at www.thebinaryrefinery.cjb.net |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
