BP Logo
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 Go to next message
Headrock

 
Messages:1772
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.


Re: A* pathing, only for non-NPCs?[message #246104] Thu, 04 March 2010 03:17 Go to previous messageGo to next message
Marlboro Man

 
Messages:1187
Registered:October 2005
Location: USA
A* is not bad in a sense, it was only bad because the dude that wrote it, added it to the main source code with out testing it, and also not telling any of the team members who were in charge of updating the main trunk about it 1st. And it all snowballed into a chaotic mess. Anyway...the dude never got a chance to fix the bugs in it. It's too bad really. So......anyway. Hope you get this to work. Smile


Re: A* pathing, only for non-NPCs?[message #246106] Thu, 04 March 2010 03:29 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
That's what I'm trying to ascertain - what the bugs were, and whether it's safe to turn A* on for characters who don't have profiles (I.E. scripts)

Because from what I understand, A* is superior in terms of its usefulness.


Re: A* pathing, only for non-NPCs?[message #246111] Thu, 04 March 2010 05:02 Go to previous messageGo to next message
lei75jkt

 
Messages:11
Registered:February 2010
Location: Indonesia
i'm must be not here when the A* is introduced, care to point me what is A*, i'm just curious that's all. oh btw i'm a web programmer using php, .net for almost 10 years, not familiar with c++ and game programming but i willing to learn and look into the source code.

How to grab the latest ja 1.13 source code ?
Re: A* pathing, only for non-NPCs?[message #246126] Thu, 04 March 2010 11:11 Go to previous messageGo to next message
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.
Re: A* pathing, only for non-NPCs?[message #246127] Thu, 04 March 2010 11:19 Go to previous messageGo to next message
DepressivesBrot

 
Messages:3691
Registered:July 2009
@ Lei
For the source code:
there are 2 stickied threads below above this one, one dealing with the general use of SVN and one containing the location of the source code


Re: A* pathing, only for non-NPCs?[message #246129] Thu, 04 March 2010 12:23 Go to previous messageGo to next message
lei75jkt

 
Messages:11
Registered:February 2010
Location: Indonesia
ok, many thanks , will check it soon
Re: A* pathing, only for non-NPCs?[message #246130] Thu, 04 March 2010 13:49 Go to previous messageGo to next message
Kaerar

 
Messages:2031
Registered:January 2003
Location: Australia :D
Yeah problem with A* is that it caused the default edge of movement to be different and along with other inconsistencies this broke the normal movement paths for NPC's. The internal algorithm for movement isn't too bad, but the AI suffers either way. Less climbing and less flanking with normal. Total idiocy with A*.

Oh and it was only turned off relatively recently. In fact I believe it was about the time of HAM 3.6 Alpha something or other.


Re: A* pathing, only for non-NPCs?[message #246132] Thu, 04 March 2010 13:57 Go to previous messageGo to next message
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.
Re: A* pathing, only for non-NPCs?[message #246142] Thu, 04 March 2010 15:04 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Well it looks like the important part of the A* formula, the one that's supposed to get characters to find the most PROTECTED path, is incomplete and deactivated, but is still in the code. Probably ADB never had the chance to complete it. If I could turn it on somehow, maybe the whole thing will perform much better.
Don't worry though, I'm going to keep this thing turned off for PCs and NPCs regardless of how well it works, and turned off for other AI until we're all perfectly sure it works. That is, if I can fix the damn thing to begin with.

P.S. the AI avoids light in normal pathing? I've never seen that before A*... And I can't get enemies to climb roofs in either system. This is very bizarre.


Re: A* pathing, only for non-NPCs?[message #246144] Thu, 04 March 2010 15:11 Go to previous messageGo to next message
wanne (aka RoWa21)

 
Messages:1971
Registered:October 2005
Location: Austria
@Headrock: I can confirm, that enemies climb on roof in A* and with A* disabled. Once, some months ago, enemies only climbed on rooftops only with A* enabled. But that is fixed.

Enable GABBY cheat, put your merc on a rooftop, let some enemies spawn (I think it is ALT + B) near the building and shoot a few times. You will see they climb up to you ...



Re: A* pathing, only for non-NPCs?[message #246145] Thu, 04 March 2010 15:17 Go to previous messageGo to next message
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...
Re: A* pathing, only for non-NPCs?[message #246147] Thu, 04 March 2010 15:24 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
@ Scorpion: There's a difference between a function not working as it should, and a function not working because it can't. If A* can be fixed, it should be far superior (for non-NPCs). The question is how to fix it.


Re: A* pathing, only for non-NPCs?[message #246160] Thu, 04 March 2010 16:17 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Goddamn, for the life of me I can't figure out how/when/why/who/if the AI even takes light into account when moving, A* or otherwise.

However in the meanwhile I'm making some headway in making A* a bit smarter. Maybe I can actually make a difference with this thing. Probably not.


Re: A* pathing, only for non-NPCs?[message #246170] Thu, 04 March 2010 17:18 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Ok, I've just added a seriously makeshift cover calculation to A* pathing. AI should now take cover into account while creating a path. I'm hoping that this will improve its behavior, but this is a very early draft. Going to test the drassen counterattack to see whether this changes anything.


Re: A* pathing, only for non-NPCs?[message #246173] Thu, 04 March 2010 17:43 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
LOL HAHAHAHA it works fantastic! Enemies and Militia try to pick paths that offer better protection while moving!

There's only one problem with this.

IT'S FUCKING SLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWW

I'm not a good enough programmer to cut down the calculation times required, I'm afraid. Sad

Maybe someone would like to take a look?


Re: A* pathing, only for non-NPCs?[message #246174] Thu, 04 March 2010 18:13 Go to previous messageGo to next message
Mauser

 
Messages:769
Registered:August 2006
Location: Bavaria - Germany
nice work headrock! i never doubted you can do it.

now, surely there

☆★GL★☆
Re: A* pathing, only for non-NPCs?[message #246178] Thu, 04 March 2010 19:38 Go to previous messageGo to next message
Kaerar

 
Messages:2031
Registered:January 2003
Location: Australia :D
Headrock
There's only one problem with this.

IT'S FUCKING SLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWW

I'm no programmer, but have you tried it in windowed mode? It might just run a wee bit quicker Wink


Re: A* pathing, only for non-NPCs?[message #246179] Thu, 04 March 2010 19:49 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
It IS in Windowed Mode. And RELEASE build. It Debug it was virtually impossible to play at all, and I haven't tried full-screen yet. Regardless, this is far too heavy for actual use.


Re: A* pathing, only for non-NPCs?[message #246180] Thu, 04 March 2010 20:54 Go to previous messageGo to next message
Marlboro Man

 
Messages:1187
Registered:October 2005
Location: USA
Sure, I'll have a look. Ahhh, there's your problem, your deflabulator is cross connected to your hydroejactulator, just jam a screwdriver between them and rotate it 14 degrees from top dead center and that should solve your problem. As for your program problem I have not a clue sorry, but your Anti-inflatulator should run perfectly now.



Your welcome.


Mr.Handy


Re: A* pathing, only for non-NPCs?[message #246181] Thu, 04 March 2010 21:15 Go to previous messageGo to next message
wanne (aka RoWa21)

 
Messages:1971
Registered:October 2005
Location: Austria
Headrock
LOL HAHAHAHA it works fantastic! Enemies and Militia try to pick paths that offer better protection while moving!

There's only one problem with this.

IT'S FUCKING SLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWW

I'm not a good enough programmer to cut down the calculation times required, I'm afraid. Sad

Maybe someone would like to take a look?


For Big Maps, A* was extremly slow (and not playable) compared to "normal" pathing. If we cannot optimize the A* pathing, we should not use it. That's my opinion.


Re: A* pathing, only for non-NPCs?[message #246183] Thu, 04 March 2010 21:45 Go to previous messageGo to next message
Khor1255

 
Messages:1818
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

Re: A* pathing, only for non-NPCs?[message #246185] Thu, 04 March 2010 22:48 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Quote:
For Big Maps, A* was extremly slow (and not playable) compared to "normal" pathing. If we cannot optimize the A* pathing, we should not use it. That's my opinion.


That's odd. I don't see why the size of the map should make any difference. A* isn't supposed to get slower when using a larger area, only when scanning for possible destinations within that area - which is handled outside of A* anyway.


Re: A* pathing, only for non-NPCs?[message #246186] Thu, 04 March 2010 22:53 Go to previous messageGo to next message
the scorpion

 
Messages:1834
Registered:September 2004
Location: CH
Khor1255
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.


megaupload is a site where large stuff can be uploaded. It's certainly not wrong to have this stored somehwere. Smile
Re: A* pathing, only for non-NPCs?[message #246197] Fri, 05 March 2010 03:53 Go to previous messageGo to next message
Kaerar

 
Messages:2031
Registered:January 2003
Location: Australia :D
Mediafire is better along with A-Drive Wink
They are far less annoying than MU and Rapidshare.


Re: A* pathing, only for non-NPCs?[message #246201] Fri, 05 March 2010 04:51 Go to previous messageGo to next message
lei75jkt

 
Messages:11
Registered:February 2010
Location: Indonesia
Damn, i'm not good with math calculations. Got C Minus in Calculus Embarrassed
but thanks for those who pointing to the svn source code. For other who want to know about A* pathing, here a link to open up your mind http://en.wikipedia.org/wiki/A*_search_algorithm, btw reading the wiki content for A* pathing in wiki makes me dizzy Embarrassed , but will try it anyway to understand more about it in the weekend and will look into the source code in case i can help with other issue

Re: A* pathing, only for non-NPCs?[message #246203] Fri, 05 March 2010 05:32 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Yeah it's not really about maths so much. It's actually fairly simple to understand. I build an A* for a Colonization clone I was starting to make, it actually worked, and I know nothing about maths.

Anyhow thanks for the offer of help. What I really need now though is a good program engineer, maybe he'll be able to help streamline the algorithm to take less CPU power.


Re: A* pathing, only for non-NPCs?[message #246205] Fri, 05 March 2010 06:34 Go to previous messageGo to next message
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

Re: A* pathing, only for non-NPCs?[message #246206] Fri, 05 March 2010 07:25 Go to previous messageGo to next message
Kaerar

 
Messages:2031
Registered:January 2003
Location: Australia :D
LOL making JA2 multi-threaded! That would be the day Smile


Re: A* pathing, only for non-NPCs?[message #246207] Fri, 05 March 2010 08:37 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Quote:
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


That's great, maybe you can replace me. I need a vacation of about 5 years.


Re: A* pathing, only for non-NPCs?[message #246218] Fri, 05 March 2010 12:01 Go to previous messageGo to next message
lochkartenman

 
Messages:25
Registered:April 2008
Location: Braunschweig, Germany
Kaerar
LOL making JA2 multi-threaded! That would be the day Smile


It is very questionable whether multiple threads would do any good given the fact that the code base is cluttered with (not yet understood) interdependencies. Multi-threading easily leads to more, very subtle bugs that are close to impossible to track down since they are hard to reproduce due to massively depending on hardware and current system load.

I did some real-time C++ programming recently (avionics software) and can tell you that even getting the very basic constructs, such as threads, mutexes and semaphores right can be very hard. Employing these constructs correctly is at least as hard. If JA were written using any kind of framework that already included threading stuff (say .NET, Qt) things would be much easier. Unfortunately this is not the case. And even if it were, the problem of numerous interdependencies within the code would remain.

Re: A* pathing, only for non-NPCs?[message #246220] Fri, 05 March 2010 12:35 Go to previous messageGo to next message
Deane

 
Messages:61
Registered:January 2010
May I humbly ask how you actually go on to calculate the pathing? Perhaps we can see which part are choking the calculation.
Re: A* pathing, only for non-NPCs?[message #246221] Fri, 05 March 2010 12:50 Go to previous messageGo to next message
lochkartenman

 
Messages:25
Registered:April 2008
Location: Braunschweig, Germany
I second that. Could you post the relevant part of the code?
Re: A* pathing, only for non-NPCs?[message #246268] Sat, 06 March 2010 00:47 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
@ Lock:

Good to know there are still people coming here with programming experience, that is like pure gold around here.

As to the A* code, I'm actually going to put that aside for the moment. It won't be easy to post anyway, since it's all a massive bunch of subfunctions (not mine, using the game's inherent Cover Calculation code). I just tried to hook them all up together, and I guess they are too heavy to be run for each individual tile along the path.

If you're interested, you could have a look at the various functions. Do you know how to get the trunk source?


Re: A* pathing, only for non-NPCs?[message #246271] Sat, 06 March 2010 03:44 Go to previous messageGo to next message
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.
Re: A* pathing, only for non-NPCs?[message #246272] Sat, 06 March 2010 03:57 Go to previous messageGo to next message
Headrock

 
Messages:1772
Registered:March 2006
Location: Jerusalem
Quote:
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.


The graphics are ecch, no one likes them. But in general you should have a go at anything you find interesting. Externalization is always in demand, of course. Possibly the best thing that can be done is removing limitations, especially things that are specific to JA2, and placing them in XMLs or INIs instead. That way people making mods don't need to worry about having a feature from JA2 that they don't like. Externalizing the binary files is of course also in high demand. I was going to try externalizing the .NPC script data files, but I'm not looking forward to it in general.

The bottom line - just do what you enjoy, we can probably all benefit from anything you might have to offer.


Re: A* pathing, only for non-NPCs?[message #246279] Sat, 06 March 2010 10:00 Go to previous messageGo to next message
Telpscorei

 
Messages:13
Registered:September 2007
Location: United Kingdom
Headrock
Goddamn, for the life of me I can't figure out how/when/why/who/if the AI even takes light into account when moving, A* or otherwise.


DecideActionRed in DecideAction.cpp around line 2460. Doesn't seem to care if the AI can see an opponent.

And yeah, I'll take a look at the A* algorithm if you have it. 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.
Re: A* pathing, only for non-NPCs?[message #246284] Sat, 06 March 2010 12:49 Go to previous messageGo to next message
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.
Re: A* pathing, only for non-NPCs?[message #246285] Sat, 06 March 2010 12:52 Go to previous messageGo to next message
Khor1255

 
Messages:1818
Registered:August 2003
Location: Pleasantville, NJ
That would be a dream come true for modders. Thanks for this.
Re: A* pathing, only for non-NPCs?[message #246292] Sat, 06 March 2010 18:17 Go to previous messageGo to previous message
Headrock

 
Messages:1772
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. Sad 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.


Previous Topic: HAM 3.6 Alpha - RELEASED
Next Topic: All mercs have a chance to learn new traits?
Goto Forum:
  


Current Time: Sat Jan 22 23:20:13 EET 2022

Total time taken to generate the page: 0.01815 seconds