Performance Optimized Vision Detection?

[Max]

Hi, I have some more questions about the workings of Phaser. First – here is what I'm trying to do:

I'm trying to make an AI for zombie characters in my Zelda-esque top-down game where if a "human" character is within a certain range of a zombie, that zombie will start hunting it down.

I've been thinking about how to approach this because at the moment I have all game objects in one big group to allow for easy z sorting. I've read in other threads that you can't have objects in multiple groups and I just have no idea how to start.

A naive approach would be to just store all humans in an array and all zombies in an array and then in update do something like this:
 

humans.forEach(function(human) {	zombies.forEach(function(zombie) {		if (zombie.canSee(human)) {			zombie.chase(human);		}	});});

This should work to get the AI on its feet but of course there are 0 performance optimizations here. If I have a few hundred humans in my game and a few hundred zombies, then this will be extremely slow. I've read somewhere that Phaser already uses quad trees for collision detection so maybe I can use them to write some performance optimized "vision detection"?

 

I think I'm looking for a way, in the zombie's update-method, to get all game objects within a certain radius.

 

Can anybody help me with this?

 

Thank you very much!

[Dumtard]

Any type of spatial partitioning should work, Phasers QuadTree implementation you could use. I have never used it but from a quick glance it seems like you could change your code snippet just a little bit to use it something like this:

var humanTree = new QuadTree(0, 0, worldWidth, worldHeight);humanTree.populate(humans);zombies.forEach(function(zombie) {    var humanRange = new Rectangle(zombie.x - (viewrange / 2), zombie.y - (viewrange / 2), viewrange, viewrange);    var potentialTargets = humanTree.retrieve(humanRange);        for (var i = 0; i < potentialTargets.length; ++i) {        if (zombie.canSee(potentialTargets[i])) {            zombie.chase(potentialTargets[i]);            break;        }    }}

[lewster32]

This is actually quite an advanced problem, for which there are many partial solutions but no perfect ones. The problem is that in order to get objects within a radius, you have to check all objects to see if they lie within that radius. There are no real shortcuts here.

 

One thing that Phaser does in its Arcade physics system is use a QuadTree as you rightly guess, which allows it to efficiently partition the objects in the world into rectangular areas, and then quickly eliminate batches of objects which aren't in the same rectangular area as the object you're trying to test the collision with. Because the QuadTree object is available for you to use, with a bit of research you could implement it into your own system.

 

This example shows the QuadTree in action: http://examples.phaser.io/_site/view_full.html?d=arcade%20physics&f=quadtree+-+collision+infos.js&t=quadtree%20-%20collision%20infos

[Max]

This is actually quite an advanced problem, for which there are many partial solutions but no perfect ones. The problem is that in order to get objects within a radius, you have to check all objects to see if they lie within that radius. There are no real shortcuts here.

 

One thing that Phaser does in its Arcade physics system is use a QuadTree as you rightly guess, which allows it to efficiently partition the objects in the world into rectangular areas, and then quickly eliminate batches of objects which aren't in the same rectangular area as the object you're trying to test the collision with. Because the QuadTree object is available for you to use, with a bit of research you could implement it into your own system.

 

This example shows the QuadTree in action: http://examples.phaser.io/_site/view_full.html?d=arcade%20physics&f=quadtree+-+collision+infos.js&t=quadtree%20-%20collision%20infos

 

Thank you very much, I think I can use the retrieve method on the QuadTree-object with a rectangle as an approximation for the vision radius. Maybe you know one more thing that has been on my mind for a few days. Is it possible in Phaser to, somewhere, get a list of all objects of a certain type? For example: all Sprite-objects or all Image-objects?

[lewster32]

All of Phaser's built in objects have a 'type' property, which corresponds to the constants defined here: http://docs.phaser.io/Phaser.js.html#sunlight-1-line-4

 

So checking a Sprite will return the following:

var sprite = game.add.sprite();console.log(sprite.type === Phaser.SPRITE)> true

You can also do it this way but I suspect it may be slower and/or fraught with perils (appealing to JavaScript gurus here to step in and tell me why this may be bad!)

console.log(sprite instanceof Phaser.Sprite);> true

[Max]

 

All of Phaser's built in objects have a 'type' property, which corresponds to the constants defined here: http://docs.phaser.io/Phaser.js.html#sunlight-1-line-4

 

So checking a Sprite will return the following:

var sprite = game.add.sprite();console.log(sprite.type === Phaser.SPRITE)> true

You can also do it this way but I suspect it may be slower and/or fraught with perils (appealing to JavaScript gurus here to step in and tell me why this may be bad!)

console.log(sprite instanceof Phaser.Sprite);> true

 

Hey Lewis, thanks for the reply. My question was more: is there a way to get a flat list of objects that are in game?

 

If I have a group with all my game objects on it and add it to the game, then iterate through every object in the world with game.world.forEach, I only get the single group.

 

I am looking for a property or method that has all "real" game objects (not groups) on it so I can avoid having to recursively iterate through all the groups (which I heard can be performance intensive). Even better would be something like game.world.getAll(Phaser.SPRITE) or something, but that would probably only make sense if the objects were stored in a hash map internally. Otherwise, I could just iterate through the objects myself.

 

Do you know if there is a method that returns all "real" game objects (without the groups) in a flat array? Or is recursively iterating through groups in game.world the only way to get these objects?

[lewster32]

Recursion is the only way unless you specifically add a reference to them to an array whenever you create them - the scene graph which Phaser uses is a tree of nested objects with game.world at the root. If you're careful about your management then it shouldn't be too hard to have a flat array of every object you've added to the game which you can then refer to.

[wayfinder]

May it be possible to extend the classes with functions that make them add themselves to a specified list, and then call that so that every instance of the class executes it? I thought i saw such a call somewhere in the code, but i don't recall the exact syntax...

[Max]

Recursion is the only way unless you specifically add a reference to them to an array whenever you create them - the scene graph which Phaser uses is a tree of nested objects with game.world at the root. If you're careful about your management then it shouldn't be too hard to have a flat array of every object you've added to the game which you can then refer to.

 

Ok, I see. Any suggestions for a clean implementation of managing such a list? Thinking about extending Phaser.Game (is this a common pattern or should I avoid extending Phaser.Game?) and adding factories for my game objects to it. That factory would instantiate the game object of the specified type, add it to an array and listen for the destroy event in which case it will be removed from the list again.

 

May it be possible to extend the classes with functions that make them add themselves to a specified list, and then call that so that every instance of the class executes it? I thought i saw such a call somewhere in the code, but i don't recall the exact syntax...

 

Thanks for the input, wayfinder. I thought about that but it might make extending those game objects difficult. What do you think of the approach I described above?

 

Thanks for your help, guys!

[lewster32]

The factory method is perfectly valid, though rather than extending Game (which seems overkill in the extreme) you may want to instead extend GameObjectFactory and then replace the game.add instance of it with your extended version.

[Max]

The factory method is perfectly valid, though rather than extending Game (which seems overkill in the extreme) you may want to instead extend GameObjectFactory and then replace the game.add instance of it with your extended version.

 

Great idea, thank you!

[Max]

The factory method is perfectly valid, though rather than extending Game (which seems overkill in the extreme) you may want to instead extend GameObjectFactory and then replace the game.add instance of it with your extended version.

 

Just following up here. I managed to override the GameObjectCreator of game.make but I had to extend Game and override the boot-method to get it work:

var entities = {};var Game = function() {	Phaser.Game.apply(this, arguments);};util.inherits(Game, Phaser.Game);Game.prototype.boot = function() {	Phaser.Game.prototype.boot.apply(this, arguments);	this.make = new GameObjectCreator(this, entities);};

Overriding game.make after instantiation does not work because game.make is still null at that point until game.boot gets called. Not sure if there is a cleaner way to this.

[Max]

 

Any type of spatial partitioning should work, Phasers QuadTree implementation you could use. I have never used it but from a quick glance it seems like you could change your code snippet just a little bit to use it something like this:

 

 

I'm sorry, I only just saw your reply. Thank you very much for your help and the code example.