Agent Ray Frustrums

Hi all,

Me and marius came up with a very nice idea to give agents "eyes".



Each agent has 6 frustrums (this can be changed), a frustrum in each of the 6 directions covering the entire area around the agent. This frustrums will shoot off a selected number of Rays. These rays will feed entities in a buffer. If another ray has already entered the entity in the buffer, the new entry is ignored.



Then after all , the RayInterpreter (or whatever it will be called) will make sense of the gathered entities. Ofcourse making sense of these entities is an applicated dependant thing and so it will be abstract.



Any thoughts regarding this?

one thing tho:



Most models consist of many trimeshes; Head, torso, legs, arms.



So when a ray intersects the Node named “model”, he wont obtain the “model”, hes going to obtain head or torso or legs…etc



So how would I be able to obtain an entity from a spatial’s child?



Marius suggested to create a new node which can be flagged as having an entity. And a back-tracking procedure would occur until the flag is met and then the entity is obtained from that node.



But what if the picked spatial doesn’t have an entity, neither do all its 1000 parents? teh AI system would have to keep looking through all the 1000 parents until it gives up!



So another solution…anyone got any ideas?



DP

I got it…



The original plans for “constructEntitySpatialRelations()” method has been…extended.



The plan was to getSpatial() from the entity and add to the hashmap.



The plan now is to getSpatial() from the entity and examine it. If its a node, then obtain children’s spatials and examine if they are nodes too. If they are not nodes, then add to the hashmap the spatial and the entity that the original parent came from as the entity.



And when a ray collision occurs, simply do “AISystem.getEntity(collisionResults.getNode(0));” and you’ve got yourself an entity!



How cool is that!



DP

This sounds cool, DP. I have a couple questions, though.



So… these rays will intersect with objects and look it up to see if it’s an entity… right? What about non-entities? Eg, the bot is standing on a street, looking down it. It shoots out its ‘rays’, and intersects with a car barreling towards it. The car is not an entity because it has no AI (maybe I’m wrong about that, though?). The bot ignores the car, and gets run over when it really would have moved had it known.



So… how does this work? Is everything in the game supposed to be an entity? If so… that mapping is going to be HUGE.



Is there any way we could try localizing the entities? Say, divide a game up into zones or levels or something… whatever the game designer wants… and keep entities grouped by zone?



This could be done with multiple AI systems… which we may not be able to do if the methods are static. I don’t know how that all fell through… is it still a static-method system, or did you turn it into a singleton with the whole ‘getInstance’ thing? If it’s a ‘getInstance’, it should be trivial to create multiple AI systems within a single game… you could just provide a ‘getInstance’ with an id that could be looked up to get the correct AI system.



This would allow the option (and it would be optional… you could always just use a single AI system) of keeping things localized… so everything doesn’t have to know about everything else. Just an idea.





That aside… I had another thought on these rays that shoot out. I’d be concerned about the performance of this… If you have AIs all over the place, this is going to consume a lot of processing power to do all these checks.



Maybe you could make the rays configurable? For example, the bot could only shoot out a few rays in one general direction (ie, whatever way it’s facing). You could also specify the number of rays… more meaning the bot will notice more things.



Anyway… just some rambling thoughts. I don’t want to overload you with stuff… but it’d probably be easier to do this up front than adding it in later.



All in all, very cool stuff. Good work.





–K

Well, an AI object will be controlling the car yes?



In a car situation, both the driver and the vehicle would be the spatial that is referenced by the driver’s entity. So to make it smarter.



Yes ofcourse the rays and the frustrums will be configurable. Each frustrum would have a variable to set how “smart” that frustrum is. Depending on that variable, a larger number of rays will be fired from that frustrum.



Ofcourse, 6 frustrums might not be needed. E.g. in a human, only 1 is needed which covers 145 degrees infront. In the common house fly, you need 5 for a realistic effect.



My only problem is the intersection. Idealy, i would like to prevent another ray from firing in a particular direction if it will obtain an entity that already exists in the buffer. But that would be overkill and would just be better to obtain the entity and and check against the buffer which the current plan is.



Also one of my concerns are, is that the rays will be fired at random and they wont be fired every frame ( performance reasons ). So at one check, they could fire in all directions except the center completely missing the entity of the car thats hurdeling towards the agent. So a “focus” point in a frustrum would have to be in order whereby a set ( or configurable?) set of the total number of rays in that frustrum will go towards that area. Idealy also, a Neural Network would be implemented to process these entities without resulting in a HUGE number of if statements.



Hope that answers some of your questions and possibly raises more.



DP

First… an AI might not be driving the car. Could be a player-controlled thing. I don’t know if that changes anything, but I just want to clarify the example.



My point was that the AI’s eyes shouldn’t just see other AI-based objects. There are all kinds of situations where it will need to see other types of things and react to them. The reactions would obviously be up to the programmer… but making it impossible for the AI to see things makes it impossible for the programmer to use the ‘sight’ to do anything about those things.



You know the system way better than I do… Maybe it’s not an issue? Is everything a Entity/Spatial regardless of whether or not it’s related to an AI?



All that aside… I’m curious about your neural-networks comment. How do you envision the neural network working to process the entities? (Not knocking the idea… I’m just curious/interested.)





–K

typically speaking, the input system will relay messages to the entity of the car, which calls AgentActions. Not everthing needs an entity. E.g. a rock, or a building, lampost (if it doesn’t fall down that is). So my AI system currently isn’t just for NPC, the player can act as an Agent too which makes this AI System so nice in my opinion. Because there is no distinction in the way things are handeled between the player and the NPC or agent.



About neural networks, i haven’t read about them much, but the idea behind them is to ellimated the if…else if statements by providing some complex machanism. AI related, it will process whatever information it can obtain from the entities without resulting in a LOAD of if statements.



Hope that explains some stuff, DP

Thanks for the explanation of the Entity/AgentAction stuff. I think I’m with you on that now. (I really need to get back into working on code again so I can play with some of this stuff… it’s been weeks.)



As for neural networks… It’s been a while, so bare with me…



Neural networks are primarily used for matching patterns of some kind… typically multiple patterns at the same time. Ie, if you have X as input and you want Y as output… but you also want A as input and want B as output (or whatever)… You can obviously do that with if-else type statements, but a neural network can, in theory, do the same thing. The more input/output pairs you have, the more efficient it is to use a network. That is, the cost of using an if-else listing will grow linearly.

With a neural network, the overhead involved is relatively constant (it’s based on the size of the network), no matter how many input/output pairs there are.



The problem with them is that they have to be ‘trained’. You feed them input and tell them what you want as outputs. After doing this a lot of times, it “learns” this behavior, and can then replicate it on demand. Also, theoretically speaking, if shown something similar to one of the inputs, it can give you the most-likely output that goes with it.



They basically work by having lots of ‘neurons’ in a mesh… Eg, one neuron connects to others (but usually not 2-way). Each neuron will have a threshold value which will cause it to ‘fire’ a signal. Ie, if it gets an inputs higher than its threshold, it sends a signal to its connected neurons. All the neurons are constantly updating their state based on their inputs. Eventually, after feeding it the inputs enough times, it learns what you want it to do with those inputs and will reliably reproduce those results.



Again, it’s been a while, and I’ve forgotten some of the implementation details on this… but that’s the general idea.



This is all kind of fuzzy, though… it’s tough to guarantee it will work. Also… as you’re training the net, it’s constantly changing… meaning you might break a previous thing that was working.



The upside is, after you get one trained, it can match things very quickly. Its real power comes from the partial matching, though… which is probably something you don’t want. I’m guessing you want exact matching only – you don’t want the actions of a monster to get results for, say, a car. I’m not sure it’s possible to do that efficiently. You might just be better off with a HashMap and some callback objects.



BUT… neural networks are cool… and would be very helpful to train an AI on what it should do given certain situations as the game progresses. Alternatively, it may be possible to use a genetic algorithm to learn.



One possible adaptation of the standard genetic algorthim could go something like this: An AI tries something. If it works, it promotes the behavior. If it doesn’t work, it slightly randomly ‘mutates’ what it does. If that works, you keep the mutation. If it doesn’t, you demote it. Keep going indefinitely, or you have a certain percentage of successes. Basically, your bots get smarter based on what’s going on in the game. As players learn new tricks/exploits (particularly ones you hadn’t thought of), the system can adapt to them to counter-act what the player is doing.



Mind you… None of this is particularly easy to program. Especially in a generic way – all AI stuff tends to be application specific because the types of input are so specialized. But, there may be some ways it can be done… Eg, providing the neural network mesh, but leaving it up to the user (programmer) to tell you how good the result is. Or… providing the mutation algorithms/generations/evolution… but requiring the user to provide you with things in a numerical format… and for the them to tell you whether or not it was a good mutation. Something like that.



That’s my very brief crash course on neural networks and genetic algorithms. It’s been about 5 years since I’ve done anything with this stuff, though… and I’ve never written a program to utilize the concepts (We studied how they were written, but didn’t actually do it ourselves… It was more of a conceptual class.)



Hope that helps. (Not that you were asking… :smiley: )



–K

wow. Thats a better explanation that all of those sites ive visited.



Ive never taken a course in my life. All this coding just comes straight from up there in the head region. This neural network stuff sounds very exciting and yet, very very very hard to program in a generic way.



We’l see how we can get it working after we finish this whole ray-boundingVolume-getEntity thing…



DP

Ive just had an idea regarding the Neural Networks…



What if you could save the state of the entire network? And then simply "plug" it into another game?



A very good example would be pedestrians. You could have the exact same AI in all of: GTA, Driver, Spiderman, Himan.



So you would have an editor of some sort to "train" the network. Then when you think that this is sufficiently clever, then just save the state.



Sticking with our car example, we could keep raming a car into a pedestrian until they know how to get away from it. Then just save the state and plug it in to the rest of the pedestrians.



How hard (because it wont be easy!) to code this, i dont know. But we could perhaps agree on some sort of file format.



DP


What if you could save the state of the entire network? And then simply "plug" it into another game?


That's exactly what you'd want to do.. particularly saving the state of the network. Ie: You tell the network to not update itself as it analizes input. You'll want to build in that possibility into the network no matter what. (For runtime efficiency, you might want to actually create two similar pieces of code -- one for an adaptable network, and one for a static network that can load the state of an existing network).

I don't know how easy it would be to port behaviors across games, but it's very likely possible. One issue is that if the game designer wants those pedestrians to have a unique behavior not defined in the provided neural network, he wouldn't be able to add it.

Maybe a combination of a behavior-map lookup, and using the neural network as a fallback? Dunno.

The biggest problem is that the network is ALWAYS going to give you a response to your input, whether or not its the one you would have wanted.

The big benefit of that is that similar problems that you didn't plan for can cause responses that make sense.

Eg: A car is charging toward a pedestrian. You plan for that, and build into your network that the pedestrian's response is to run out of the way. Then, take the case of, say.. a wrecking ball swinging down out of the air toward the pedestrian. That's something charging toward the pedestrian, but not something you planned on. Running it through the neural network has a decent possibility of getting the 'run out of the way' response.

I like the idea of the editor to train the network.. it could help the game designer to set up behaviors. One similar idea would be to flag the neural network system as 'trainable' or not, and to print output in a certain way (and save to a file on demand?). Then, the game designer could just play the game, and create the situations that he wants the AIs to handle (eg: Drive the car at the pedestrian.). Either of these (editor or in-game) would probably be very challenging to program, though.. I'm not really sure. The in-game version might be better suited toward a genetic algorithm solution.

Somehow, you have to tell the neural network that there is a particular input it should learn, and what you want the output to be.. You also have to keep in mind that there are other stimuli in the game that could confuse the AI. I'm not sure how well a network could come up with a behavior combination based on multiple stimuli. That's kind of a neat possibility.. but implies not having concrete responses... which leads into fuzzy logic.

Fuzzy logic is basically this: The amount of reaction is based on the difference from the average of the stimulus.

For example, using our car.. The faster a car is charging toward a pedestrian, the faster it will move out of the way. If the car is moving very slowly, the pedestrian will just slowly move out of the way instead of running.

I dunno.. maybe that's too complicated. I was just trying to think of a way to use all numbers in the neural network so that it can be more generic. Instead of messing with fuzzy logic like that.. maybe we could just ask the network for the 'strength' of the match it made. Ie, it gives you an output, but you aren't sure if that's exactly the output you wanted. You could ask the network (say on a scale of 0 to 1) how good of a match it is, and adjust accordingly. (Eg, a poor match may make the pedestrian 'confused' for a few moments before taking the action)

Anyway.. I'm rambling.

When it comes to working on the neural network itself, coming up with a standard file format is probably a good idea.


--K

I just had an idea, that really makes “Rays” obselete.



I foresaw a problem with the ray model. The ray kept on going indefinetly in the direction it was heading. So even if the agent is like 7000000 miles away, you can still see him?!



So instead of doing Ray-Spatial collision detection, im going to do Frustrum-Spatial Collision Detection.



This also makes up for the possibility that the agent is right infront of you, but you cant see him because the rays aren’t there.



What ya think?



DP

I have no idea what ‘Frustum-Spatial Collision Detection’ is. :slight_smile:



If you don’t mind… What does it do, and how would it work?





–K

A frustrum is a truncated pyramid.



So its like a normal pyramid, but its head is chopped of. Theres some clever mathmatical formula to see if something is inside or outside that frustrum.



Im going to be checking the frustrum to see if any spatials are inside, if they are, then obtain their entities if they have one. Very similar to the ray-spatial intersection.



jME sort of has this capability (actually it does in the form of the camera’s frustrum), so im going to be using something very similar.



DP

Ahh… okay. That sounds good. :slight_smile: Very likely will be more accurate and efficient than the rays.



I assume the frustrum is going to radiate outward from the object doing the ‘looking’? (Basically like a view frustrum…?)



If so, do you have any ideas on how you’re going to handle ‘looking’ in multiple directions? Just use multiple frustrums?





–K

yeah, pretty much; mutliple frustrums.



Do you remeber my dilema with the hashmaps?



Well, i think ive solved it.



The constructor of Entity will now take 2 arguments, its name, and the spatial its associated with.



What the constructor will do, is examine the type of spatial you have give it, and extract all the names of all the geometry and store it in an ArrayList.



When a collision occurs, what the AISystem basically does is loop through all the entities, check the arraylist for the geometries name and do checking.



Now if you change the spatial, the names will change, thus illiminating the memory leak.



Now i hear you saying, but what if its 1000 agents, each is associated with 50 geometries (thats 50,000 Strings to loop through). Well, the answer to that is to cut that loop into different frames. Lets call this a "feature" of "response time" rather than a defect! :wink:



What ya think? DP

I’m not sure I follow what you’re doing, actually. Let me see if I can figure out where I’m confused…


  1. You create an Entity – it has a name, and the name of the 3D object (spatial) it’s associated with.


  2. When this happens, the entity will go through the spatial and pull out all the names of the geometry in that spatial and store them in a list. This list is specific to that entity? (Is this right? I don’t think that’s what you’re saying, actually.)


  3. Later on, a collision occurs between two spatials? The AI system gets called to handle this, and checks the lists stored on the entities involved in the collision… (I don’t know… this doesn’t sound right.)


  4. If you change the spatial… somehow the names change, so it won’t get matched against later?


  5. Basically, this is supposed to elminate the memory leak of keeping a reference to a spatial around by only keeping the name of it around?


  6. There’s a problem with efficiency because of the large number of names that have to be looked through… so the solution is to do that across multiple frames somehow.





    If I’m more or less right on this… there might be a few problems.


  • How can you guarantee the that the names won’t overlap? Ie, what happens when you have two things with the same name?


  • Your list of names is going to continue to grow, and never shrink? Is there some way to remove names from the list? It sounds like you still have a memory leak here… it’s just Strings in an ArrayList instead of Entities in a HashMap. (It’s arguably better because Strings are probably smaller objects and don’t reference other things, but it’s still a problem.)


  • Splitting the checking across multiple frames sounds like a hack. :smiley: Maybe there would be some way to use a HashMap (or some kind of sorting mechanism) to do fast lookups of names instead of looping through them?


  • I don’t think you intend on having one list per entity… sounds like you plan on having a master list. This is probably going to get really cumbersome. For high-performance things, you really don’t want to loop through long lists. (I’m not saying you even CAN have separate lists… just saying that one huge “list” is going to become a big headache.)





    Is it unreasonable to make a method call when an entity is removed from the game? That’s what’s causing the problem, right? That is, if you can just notify the AI system that the entity has been removed, then you can remove it from whatever mapping you want. It would be up the the programmer to do this, and it doesn’t sound like an unreasonable requirement.



    I don’t mean for this to be a final suggestion or anything… I’m thinking of this as kind of a design review discussion… figuring out all the pros and cons of a proposal until we find something that works best. Ie: I’m not making any hard suggestions, just presenting ideas for discussion.



    So… what am I misunderstanding? (I know I’m missing something…) What do you think about the issues I’m talking about? Any ideas on how to tackle them?





    –K
  1. yes, that is what will happen


  2. yes that is what its going to do, and yes, the list is private to that entity. The Master list is already implmemented with the rootEntityNode.


  3. When a collision occurs, it will loop through all entities in this “zone” and call a method in entity which checks the entity’s arraylist to see if the spatial’s name is in that entity or not.


  4. If you change the spatial, the entity will find all the geometries in that spatial and pick out their names and overwrite the arraylist in order to remove the memory leak you were talking about.


  5. Yeah, we need some mechanism instead of a loop. If its a loop, we’l split it over x amount of frames.



    I dont think its a hack, because all of the articles ive read keep saying “you dont need to update your logic everyframe” and this is what we’re doing in a sense.



    Over lapping names…hmmm…thats a toughy. Im gonna have to think about that one.



    The memory leak has been taken care of by overwriting the entity’s arraylist instead of adding to it.



    What do you think? is this the right solution to the problem? or should I keep on thinking?



    DP

I have uploaded a new zip to my site (http://www.myjavaserver.com/~digiwired/ai-code.zip). It contains the getEntity(Spatial spat) method in AISystem.



The test for that is the same test as the TestAgentAction. It obtains the entity from a spatial’s name, and also prints out the time it takes for the process to occur (I get 0 milliseconds on my machine).



Im thinking of a way now to attach those frustrums to the entities and rotate with the spatials as well.



DP

Splitting the lookups over multiple frames because you have no choice given the design implies that you don’t want to do that. (If you want to do it because it will help a little, that sounds much better.) Imagine a game where you have a ton of things happening… that’ll be a lot of processing. My point is… For these lookups, there’s very likely a better way than just storing the names in a list.



How often do things get added to that list? Not very? Maybe a Tree is the way to go so the names could be found quickly? You could also just create a map (HashMap, probably), and put all the names in there as keys. The values would be… well, anything but null. Boolean.TRUE comes to mind… although you could just store the name as the key and the value.



Anyway… point is, you should be able to do random lookups much faster than just looping through a list.



I don’t know what to suggest about the overlapping names because I’m not really sure how the names are derived. Maybe you could automatically append an ever-increasing counter to the end of the name? (maybe with a dash (’-’), too… just in case somebody puts a number at the end of their name)



What do you mean by ‘overwriting the entity’s arraylist’? I’m not sure I follow when that would happen?



One final question/note… 0 milliseconds sounds… well, not right? I know there’s a problem on various OS’ with the milliseconds timer not being right. (I think Windows is the worst… like it only updates every 55 milliseconds or something bad like that) Anyway… just some food for thought.



I’m not sure if this is the right way to go or not… I really don’t know/understand the whole system. It sounds like it has promise, though…





–K