Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / AI in an FPS, isn't A* to slow for that?

Author
Message
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 5th Nov 2003 21:48
Link
well...I'm working on my fps and I'm wondering, how would I do the A* when the enemy's have to walk in a 3d world, like up or down, left or right and in depth? and wouldn't it be way to slow to calculate paths for like 20 enemy's through a 3d world? how is this done in other games... just doing a part of the path each loop?

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Inkybro
23
Years of Service
User Offline
Joined: 31st Dec 2002
Location: Where I live :)
Posted: 5th Nov 2003 21:54
Link
Hallo, ik snap het niet Sorry, maar, hoe gaat het met je?


http://fingaming.0wns.org/nANo/
Back to top
Profile PM Email Website
QuothTheRaven
23
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 5th Nov 2003 22:29
Link
Inky, what he said made complete sense.

Well, the A* algorythm is pretty much the pathfinding way to go, although I've never used it. I don't think the calculations would be all that slow. Heck, it worked for starcraft.

Back to top
Profile PM
apophis
23
Years of Service
User Offline
Joined: 14th Jul 2003
Location:
Posted: 5th Nov 2003 22:57
Link
One solution is dont do pathfinding. Have commands for when you get in a certain proximity of a bot strafe left or duck behind rock. You can even have the AI prepositioned and say when you get in 50 feet fire shotgun 8 times. So dont have pathfinding for all the AI bots just the ones you need at the current time. Plus all that pathfinding would make for higher system specs since it takes up RAM.
Back to top
Profile PM
Inkybro
23
Years of Service
User Offline
Joined: 31st Dec 2002
Location: Where I live :)
Posted: 5th Nov 2003 23:01
Link
Ja, maar IK snap het niet. Je snap het goed, maar ik niet.


http://fingaming.0wns.org/nANo/
Back to top
Profile PM Email Website
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 5th Nov 2003 23:10
Link
A* can be fast ... check out my code in CodeBase.

Grab the zip file - there's an example application included in it that also includes timing.
Back to top
Profile PM Email Website
Guruchild
23
Years of Service
User Offline
Joined: 13th May 2003
Location: United States
Posted: 6th Nov 2003 00:52
Link
I would use a series of if then else statements as triggers. I'm actually into this part of the programming in my game right now.

In psuedo-pseudo code, it goes something like:

For each enemy in range of your character, check to see if that character needs to be made to attack you, back off, move towards you, etc. If all the checks for a particular enemy work out, then perform the appropriate action.

This seems relatively fast, the calculations don't slow my game down any more than having the models loaded themselves does.

I have a sign beside my door-hinge, that says nothing rhymes with orange.

Soul Defender: 75% GodMode RPG: 5%
Back to top
Profile PM Email
MikeS
Retired Moderator
23
Years of Service
User Offline
Joined: 2nd Dec 2002
Location: United States
Posted: 6th Nov 2003 01:13
Link
@Inkybro

How the heck does that help?

@Mussi

Just do a search, like IanM mentioned, in the codebase. Tons of reasources.



A book? I hate book. Book is stupid.
Back to top
Profile PM Email
QuothTheRaven
23
Years of Service
User Offline
Joined: 2nd Oct 2002
Location: United States
Posted: 6th Nov 2003 06:00
Link
Quote: "
@Inkybro

How the heck does that help?
"


I've noticed a very disturbing trend between having a nano sig, and how people with nano sigs act on the forums.

I do not think very highly of "nano" right now.

Back to top
Profile PM
Andy Igoe
23
Years of Service
User Offline
Joined: 6th Oct 2002
Location: United Kingdom
Posted: 6th Nov 2003 08:04
Link
You could always use a node network as navigational waypoints. You could even bind scenic objects to the pathfinding and use it in the display routine too. Nearest 3 nav nodes show their objects or some such

The navigational code would perhaps be a bit more complicated if you want your bots intelligent, but if they are just running around like Quake it would be fairly easy to plot a route across your map to a random target node.

Pneumatic Dryll
Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 6th Nov 2003 16:19 Edited at: 6th Nov 2003 16:21
Link
IanM, i tried your code some time ago I think, but if I made the path harder to find like putting walls in it, it took some time. maybe I'll try the trigger thingie. but does anyone know how I can move the enemy in 3 dimensions? cuz I only know how it works in 2 dimensions

inkybro, gaat goed met me , misschien moeten we is over msn ofzo praten want dat is minder irritant voor de andere.

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Wolfish King
22
Years of Service
User Offline
Joined: 23rd Aug 2003
Location: The Netherlands
Posted: 6th Nov 2003 17:46
Link
Haha, cool nog meer Nederlanders en ik snapte je vraag ook niet echt.
Back to top
Profile PM
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 6th Nov 2003 19:01
Link
IanM, your code was only in 2 dimensions, so that means calculating a path with 3 dimensions would take longer, wouldn't it? still looking for an idea or tut to learn how I could be able to make A* in 3 dimensions instead of only 2

wlofish king, zijn best wel veel nederlanders op dit forum , minstens 13, en over m'n vraag... ja daar moet je een beetje erg into coding voor zij he

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 6th Nov 2003 19:31
Link
I don't know of any standard A* search for 3 dimensions - I think most fully 3D games seem use a waypoint system with a few extras added.
Back to top
Profile PM Email Website
Terabyte
23
Years of Service
User Offline
Joined: 28th Dec 2002
Location: UK
Posted: 6th Nov 2003 20:17
Link
sorry...maybe i missed somet... is this topic on ai... path's for objects?.... cus if it is.. what the hell is A*... and wats the solution..if it isnt just ignore me for te next 2 days

The following threads and their accompanying sound tracks are protected by copyright and any broadcast public diffusion, copying and edditing are etc... etc.. you may not complain about my Typo's
Back to top
Profile PM Email Website
Neophyte
23
Years of Service
User Offline
Joined: 23rd Feb 2003
Location: United States
Posted: 6th Nov 2003 20:39
Link
@TeraByte

"what the hell is A*... "

A* is a popular algorithm for pathfinding.
Back to top
Profile PM
Inkybro
23
Years of Service
User Offline
Joined: 31st Dec 2002
Location: Where I live :)
Posted: 6th Nov 2003 20:58
Link
@Yellow: Mussi understands and speaks dutch, I'm asking him how he is. You got a problem with me being friendly?

@QuothTheRaven: Read above.

Sommige mensen zijn echte klootzakken. Ik snap het Quoth niet.


http://fingaming.0wns.org/nANo/
Back to top
Profile PM Email Website
Inkybro
23
Years of Service
User Offline
Joined: 31st Dec 2002
Location: Where I live :)
Posted: 6th Nov 2003 21:04
Link
Mussi, wat is jouw msn? De mijne is [email protected], jij kan toevoegen mijn msn.


http://fingaming.0wns.org/nANo/
Back to top
Profile PM Email Website
cusoi
23
Years of Service
User Offline
Joined: 3rd Jan 2003
Location: Netherlands
Posted: 6th Nov 2003 21:13
Link
Inkybro is learning some dutch at the moment... And he's practicing with it... His Dutch is pretty good already (and that's not only because I'm the one who's teaching it to him )

Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 6th Nov 2003 21:21
Link
Quote: "I think most fully 3D games seem use a waypoint system with a few extras added. "

what kind of extras? so does this mean I have to trow a lot of waypoints in the map and just check for the most fast route? but that sounds almost like A*

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Barliesque
23
Years of Service
User Offline
Joined: 10th Nov 2002
Location: Los Angeles
Posted: 6th Nov 2003 22:26 Edited at: 6th Nov 2003 22:27
Link
You might try writing your code so that you make AI adjustments for one character at a time. So, if your main loop runs, let's say 40 times a second, and you calculate for just one character each time, then within less than a second you've done your AI calculations for all your characters. You might even be able to split the calculation up into a few stages---if it takes characters two or three seconds to work out a new path, then really that's more realistic than ALL of them reacting instantly.

...Nice avatar, by the way.

CPU: Pentium 4 3GHz, w/ Hyperthreading, 1GB DDR RAM
OS: Win XP Home, SP1, DirectX 9.1b
GPU: NVidia GeForce FX 5800, 128MB
Back to top
Profile PM Email
MikeS
Retired Moderator
23
Years of Service
User Offline
Joined: 2nd Dec 2002
Location: United States
Posted: 6th Nov 2003 23:14
Link
@Inkybro
Quote: "How the heck does that help?"

I still wanna know.

A book? I hate book. Book is stupid.
Back to top
Profile PM Email
Rob K
Retired Moderator
23
Years of Service
User Offline
Joined: 10th Sep 2002
Location: Surrey, United Kingdom
Posted: 7th Nov 2003 00:42
Link
I have an idea.

If you only have a set no. of floors in your level, eg 3, then you could create an A* move grid for each of those three levels.

If the enemy is on the same level as the player, then an A* check on the appropriate grid would work. If the player is on a different level, the enemy would first do an A* check to locate the nearest entry point to the player's floor - eg stairs (these would have to be specified just like "open" and "closed" nodes, then another A* check could be performed to calculate the route to the player from the entry point to that floor.

The grids themselves would probably have to be created out of a system of closely packed waypoints which you would have to manually create.


BLUE GUI Plugin: http://blue.robert-knight.net / BLUE IDE http://blueide.sf.net/blueide_alpha3.exe
Back to top
Profile PM Email Website
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 7th Nov 2003 09:03
Link
Think of it another way - a bot looking for a health top-up.

1) Scan the current map for the nearest health
2) Scan the current map for a way up
3) If the way up is closer than the nearest health, scan the next level up for a health and add the costs together. Keep track of the cheaper of the two
4) Scan the current map for a way down
5) If the way down is closer than the nearest health, scan the next level up for a health and add the costs together. Keep track of the cheaper of the two.

If you use the Flood check built into my routines, this is a minimum of 3 searchs, which would take about a third of a second on my laptop ...

Or an A* search to all known health top-ups on the current level, then searches for all known exits to other levels, then a search from each entrance on each level to all known health top-ups on those levels ... it soon grows out of control

I think that another method is needed - instead of using a grid, using a graph so that you could have multiple levels in the same scenery. (A graph is a set of points with connections between them, so you could even represent a teleporter this way, you could emulate the grid layout, or a hex layout, or a waypoint system by adding different costs to the vertices ...)

I have no idea at the moment of how to represent this in DBPro, and it's beyond most people here (no offence!) to actually create and use one meaningfully. Plus the routines themselves are going to be a bugger to put together, and probably won't be A*, and will possibly slower than what we have, but it would definitely be more general/flexible than the grid representation

I'll think on it some more.
Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 7th Nov 2003 15:25
Link
oke, think I might be able to put something togheter now, thanks to you guys. but it will take some time so I think I'll just keep the AI for the game that I'm making for the compo low. when that is done I'm going to start the ultimate programming challenge...programming AI

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Inkybro
23
Years of Service
User Offline
Joined: 31st Dec 2002
Location: Where I live :)
Posted: 7th Nov 2003 18:27
Link
@Yellow: Exactly how are your posts helping?

Je zijn een kutlul, klootzakken.


http://fingaming.0wns.org/nANo/
Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 8th Nov 2003 12:52
Link
hey, you two, be nice to each other, your stealing my thread
so IanM can you answer my questions above, or anybody else?

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Ermes
23
Years of Service
User Offline
Joined: 27th May 2003
Location: ITALIA
Posted: 8th Nov 2003 13:13
Link
One easyest system is to make a path for the enemy to follow, like a race game.
If the enemy get close to player one, the enemy will leave the path and pursue the player.
Once the player escaped, the enemy return to its soubroutines of path movement.
Can you code this?? it's easy.

Damned my tongue!!! and my finger, this is an help to your game to win the competition!!!

Free Download for a Free World
Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 8th Nov 2003 13:19 Edited at: 8th Nov 2003 13:20
Link
haha, thats a good idea, I think I might do that and I think I'm capeable of programming it... if not, I'll ask for some help again

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
IanM
Retired Moderator
23
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 8th Nov 2003 13:22
Link
Read my previous post from this point : 'I think that another method is needed -'
Back to top
Profile PM Email Website
Mussi
23
Years of Service
User Offline
Joined: 27th Jan 2003
Location: Netherlands
Posted: 8th Nov 2003 18:19
Link
whoops, overlooked that post of yours

Specs: AMD Athlon 1800, 256 DDRRam 266mhz, 80GB HD 7200rmp U133, Geforce 4 Ti4400 128mb ddr sdram
Back to top
Profile PM
Andy Igoe
23
Years of Service
User Offline
Joined: 6th Oct 2002
Location: United Kingdom
Posted: 9th Nov 2003 20:52
Link
Not to be too finnicky but...

Quote: "A* is a popular algorithm for pathfinding."


It's a heuristic. An algorythm is merely algebra where you know the question and want the answer. A* uses heuristics because you know the answer (the destination) but want to find the question (how to get there).

Heuristics is simply a method of points scoring possibilities, A* is a method of focusing on the most probable routes as you calculate the path so as not to have to calculate every conceiveable path.

Pneumatic Dryll
Back to top
Profile PM Email Website
Neophyte
23
Years of Service
User Offline
Joined: 23rd Feb 2003
Location: United States
Posted: 10th Nov 2003 00:30
Link
@Andy Igoe

"It's a heuristic. An algorythm is merely algebra where you know the question and want the answer. A* uses heuristics because you know the answer (the destination) but want to find the question (how to get there)."

I stand corrected.
Back to top
Profile PM
zircher
23
Years of Service
User Offline
Joined: 27th Dec 2002
Location: Oklahoma
Posted: 10th Nov 2003 02:14
Link
All well and good, but A* can be time consuming (expecially in 3D.) Waypoints are much faster and a level designer can add 'intelligence' to a way point system by placing them over power ups, through bottle necks, around hazards, and in the case of FPS games, at good sniper locations.
--
TAZ
Back to top
Profile PM Email Website
Andy Igoe
23
Years of Service
User Offline
Joined: 6th Oct 2002
Location: United Kingdom
Posted: 10th Nov 2003 02:28
Link
Quote: "I stand corrected. "


Dang, I drill you into the floor with my unbelieveable intellect and your still standing ! I'm defeated.


God created the world in 7 days, but we're still waiting for the patch.
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2026-07-26 17:34:11
Your offset time is: 2026-07-26 17:34:11