Home » MODDING HQ 1.13 » v1.13 General Development Talk » A* pathing, only for non-NPCs?
| A* pathing, only for non-NPCs?[message #246102]
|
Thu, 04 March 2010 02:04 
|
|
| Headrock |
 |
Messages:1760
Registered:March 2006
Location: Jerusalem |
|
|
I've been thinking about having enemies/militia try to avoid corpses when they move. We've all wanted this - it should help keep them alive.
However, turns out that the regular JA2 pathing isn't very good for this. In fact I don't think it even knows how to avoid well-lit areas at night. Maybe I'm wrong, but that's what I'm seeing. Heck I think it even skips rooftop climbing.
Of course, A* pathing can calculate all that shit. But as you know, it also screws up NPC movement, which is why it was eventually disabled.
But I was thinking, maybe a combination of both would be best. That is, use A* pathing for generic enemies (redshirt/blackshirts) and normal pathing for NPCs (including mercs?). I've actually managed to convince the program to do this.
The real test however is whether NPCs and non-NPCs can consistently move as they should with this system. But for that, I need to have an exact method of telling whether NPCs aren't screwed.
I know some of you have complained about A* in the past - this is a good time to voice your knowledge on this matter. It's a very simple question:
Which NPCs have movement problems when using A*, and what can you say about the difference between how they move with it turned on and off. Be as specific as you can, so I could try to recreate the same conditions and see if they still happen.
If all goes well, I'll reactivate A* for non-NPC characters, and possibly add that corpse thing.
Report message to a moderator
|
|
|
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246126]
|
Thu, 04 March 2010 11:11 
|
|
 aehchua |
 |
Messages:33
Registered:October 2007 |
|
|
A* pathing not only screws up standard JA2, but impacts other mods as well (e.g., Renegade Republic). I've noticed relatively few posts about A* on this thread, probably because people have forgotten what A* did, specifically- it was turned off some time ago. One person who should still remember is The_scorpion. He might not be able to tell you PRECISELY what A* did, but IIRC, it screwed peoples' behavior in RR.
As MM noted, there's nothing wrong with the A* algorithm. There were things wrong with the implementation in 1.13. Basically, the individual who implemented it had never played the game seriously. Some of the other things he did, for example, included deactivating fighting at night.
I suspect (I don't know) one of the problems was that people would climb roofs in aberrant ways. There might be a building between point A and B. People would probably attempt to climb the building and climb off assuming that this was the shortest path. A more optimal route might be to walk THROUGH the building.
As another potential problem (common to other games)- is the cost for walking diagonally equal to or less than the cost of walking in a straight line? If so, one might see NPCs walking a triangular route to a destination, instead of walking straight.
@Lei: You can look up A* pathing on wikipedia. It's a graph-based algorithm, where every edge has a cost of traversal. It's a (relatively) computationally inexpensive algorithm for finding the least costly way from point A to point B.
Report message to a moderator
|
Private 1st Class
|
|
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246132]
|
Thu, 04 March 2010 13:57
|
|
| the scorpion |
|
Messages:1834
Registered:September 2004
Location: CH |
|
|
Yeah, we had almost countless problems with A* on pretty much all levels and though all character types. NPC pathes were just one thing, but AI prolems and also PC pathing problems made it appear inferior to classic pathing on all levels.
Also, A* completely sucked at avoiding lit up places at night, so hoping that it would not suck for avoiding bodies seems naive to me.
Don't dig up that corpse.
Report message to a moderator
|
Sergeant Major
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246145]
|
Thu, 04 March 2010 15:17
|
|
| the scorpion |
|
Messages:1834
Registered:September 2004
Location: CH |
|
|
i don't know in how far the AI avoids lights in normal pathing.
What it did in A* is to run into it, notice the light, run out of it again. End turn. next turn, the next AI solider runs into the light source and the out of it. Rince repeat until my guys have interruptet all AI soliders on the same light spot killing all of them. Yet another example of an attempt to make the AI smarter that led to its demise.
had 7 guys in one turn just ignored the stupid light, they coulda totally messed up my snipers, but because 20 consecutive ai guys rushed into the light source, then turned back into the only dark spot (guess where my NVG wearing mercs where spotting... *duh*) and got wasted either in the light or in the dark spot that i covered, i could clean the entire sector without a trace of sweat.
Not only is this an example of A* suckage, it is also an example of not-really-thought-through attempts of making the AI react smarter. Often, it will become dumber and more predictable. Let's see what you want to do concerning the bodies. If the AI will avoid bodies most of the time, even dumb players will very soon learn to exploit that and know where to expect enemies and where they're safe because AI can't cross due to bodies lying around.
We don't design AI to react smart enough for other AI, it must also be a challenge for the player, and if just a few out of these 20 soliders would have rushed through the light source, that would have helped them big time...
Report message to a moderator
|
Sergeant Major
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246183]
|
Thu, 04 March 2010 21:45
|
|
| Khor1255 |
|
Messages:1817
Registered:August 2003
Location: Pleasantville, NJ |
|
|
Glad to hear you guys are finally coming around on this issue.
EDIT:
Oh, by the way I finally found the zipped up version of the 687 exe on a retired hd. If anyone wants to look at what was going on before this.....'upgrade' than let me know how and where to upload such a giant file.
[Updated on: Thu, 04 March 2010 21:49] by Moderator Report message to a moderator
|
Sergeant Major
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246205]
|
Fri, 05 March 2010 06:34
|
|
| lei75jkt |
 |
Messages:11
Registered:February 2010
Location: Indonesia |
|
|
true, C++ is not my thing, maybe somebody expert in C++ Concurrency programming can help you, consider all cpu is now dual core maybe a multi-threaded coding is needed. Anyway i'm not give up to study more about game programming, has been reading about game programming in c++ for the last couple days
[Updated on: Fri, 05 March 2010 06:36] by Moderator Report message to a moderator
|
Private
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246271]
|
Sat, 06 March 2010 03:44
|
|
| lochkartenman |
|
Messages:25
Registered:April 2008
Location: Braunschweig, Germany |
|
|
I have got both linux and windows running so getting the trunc should be possible (at least using linux, but I also used Tortoise before). I can also possibly get Visual Studio (2003-2008 Professional) from university if that is the preferred IDE.
I don't want to interfere with too many features to get started so maybe a simple externalization task would be most appropriate to get started with. I once looked into the graphics stuff to work with the laptop files module but to no avail due to -- at that point -- severely lacking C++ skills. The latter have improved but graphics are possibly still not my strong point.
Report message to a moderator
|
Private 1st Class
|
|
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246284]
|
Sat, 06 March 2010 12:49
|
|
| lochkartenman |
|
Messages:25
Registered:April 2008
Location: Braunschweig, Germany |
|
|
I will try to turn the *.npc files into appropriate XML-files. Let's see how far I get.
Report message to a moderator
|
Private 1st Class
|
|
|
|
|
|
| Re: A* pathing, only for non-NPCs?[message #246292]
|
Sat, 06 March 2010 18:17
|
|
| Headrock |
|
Messages:1760
Registered:March 2006
Location: Jerusalem |
|
|
Quote:DecideActionRed in DecideAction.cpp around line 2460. Doesn't seem to care if the AI can see an opponent.
Hmmmm, as I expected, the AI doesn't take lighting into account when PATHING, only when selecting a destination. Therefore it means that without A*, our enemies will keep running into lights to get to an unlit square on the other side.
The basic thing I could do is to copy this portion into DecideBLACK, so that they take lights into some consideration (With less emphasis) when they DO see enemies. However, without A* their pathing will still make obvious mistakes.  Fortunately, like with corpses, it would be much easier for me to make A* take lights into consideration - it's a MUCH less heavy check. I'll give this a go once I get my SVN branch operating.
Quote:Will see if we can't improve the time. If it's possible, can you throw the whole thing into a .doc file. It'll save me hunting around for the different functions, and complextiy analysis are easier (for me) on paper. If not, just which files and which functions and how they're strung together will do.
I'll try to compile something. Please note that the current A* code is activated by two separate DEFINES, one turns A* on and off, the other turns on something called an Extra G Cover Check, which tries to stop characters on a tile where they can change stance and get more protection. I'm not sure the second part works as intended. What I tried to do is add a check for every tile along the path, calculating an otherall "I" value for the path (Separate from G, which is AP cost), and comparing paths using both I and G. If a path is marginally more costly in G (AP cost) but provides a higher overall I (cover) value, the AI will prefer taking that path. The problem of course was that calculating a cover value was extremely expensive. To get a general idea of how the program calculates cover costs, check out the function CalcCoverValue(), which is what I used. It is very expensive, running such heavy subfunctions as "BestCTGT", "AverageCTGT" and "WorstCTGT", among others.
Quote:I will try to turn the *.npc files into appropriate XML-files. Let's see how far I get.
That would be brilliant. If you run into any trouble (don't think you will), just ask.
Report message to a moderator
|
|
|
|
|
Goto Forum:
Current Time: Sun May 05 02:09:57 GMT+3 2024
Total time taken to generate the page: 0.02911 seconds
|
Blog
Search
Help
Members
Register
Login
Home
