How to implement space-partition in ash.

[chan...@gmail.com]

Hello,

I am creating a RTS game and want to use entity-system, but there are some questions confuse me.

My quesiton is How to implement space-partition in entitiy-system.

Imageine two approaches below “component-based OOP”vs “entitiy-system”

In “component-based OOP”: component is responsible for processing logic and using message passing to coupling module.

For instance, “SpacePartition” is used to improve querying unit performance in AI.

Entity have a PositionComponent which could SetPosition and SendSyncMessage (very like invoke directly).

SpacePartitionManager subscribe PositionMoveMessage on MessageBus and handle entity’s move in SpacePartition.

 class PositionComponent
 {
     float x, y;
     public SetPosition (x, y)
     {
         if (this.x!=x && this.y!=y)
         {
             x=y; y=y;
             MessageBus.SendSyncMessage(new PositionMoveMessage(entID, x, y));
         }
     }
 }

 class SpacePartitionManager
 {
     void HandleMessage (PositionMoveMessage msg)
     {
         SpacePartition.Move(msg.entID, msg.x, msg.y); //change data in SpacePartition struct
     }
 }

 

Since using the message passing, SpacePartitionManager don’t care who changed position.
 (NB: entity’s position may be operated by physics, navigation, or other user customized behaviors which like “teleport”)

 

 

In “entitiy-system”, we could not use message passing in component (message passingis OOP concept), component have DATA only!

So we must make SpacePartitionManager become a component (SpacePartitionComponent, there is one entity in world) which include all entity’s space partition info, and call SpacePartitionComponent.SpacePartition.Move in all “moving-systems”. (which like: PhysicsSystem, FlyNavigationSystem, CrawlNavigationSystem, VehicleNavigationSystem, TeleportSystem, WanderSystem, etc)

 That’s very inconvenient, because it means all “moving-systems” will depend on SpacePartitionComponent, but in concept “moving-systems” shouldn’t depend on SpacePartitionComponent. (SpacePartitionComponent only a optimization)

 

How to handle this problem?

Any advice would be very appreciated.

 

Very thanks.

[Michael Cann]

Hmm,

If I understand you correctly then you just have a System that looks after your SpacePartition, so something like:

class SpacePartitionSystem
{
NodeList<SpacePatitionNode> spacePartitionNodes

void Update()
{
foreach(var node in spacePartitionNodes)
{
node.partitionX = node.position.x / 10; // or however your partitioning logic works
node.partitionY = node.position.y / 10; // or however your partitioning logic works
}
}
}
class SpacePatitionNode
{
public PositionComponent position;
public SpacePartitionComponent spacePartition;
}
class SpacePartitionComponent
{
float partitionX;
float partitionY;
}
class PoisitionComponent
{
float x;
float y;
}

Then you have a separate System for any part of your game that needs to handle when the movement changes.

Mike

--
You received this message because you are subscribed to the Google Groups "Ash Framework" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ash-framewor...@googlegroups.com.
Visit this group at http://groups.google.com/group/ash-framework.
For more options, visit https://groups.google.com/d/optout.

--

Mike Cann
http://www.mikecann.co.uk/

@mikeysee

[chan...@gmail.com]

Hi Michael Cann,

Thanks for replay.

But there is still some problem in your approach. (root cause is : some system need both get and set position)

For instance,

NavigationSystem will change position, but "whether it can move" and "where it move to" depend on others entity's position. (from SpacePartitionComponent)
(NB: NavigationSystem will check unit collision.)

The "get" and "set" should be in the same update layer (NavigationSystem.Update()).

If update order is :

NavigationSystem.Update()
SpacePartitionSystem.Update()

The NavigationSystem's movement will use the position on last frame instead of current frame,

For instance,

in NavigationSystem.Update():

UnitA move, check other units from SpacePartitionComponent, okey, is passable, move from pos(1,2) to pos(3,4), now UnitA is pos(3,4)

UnitB move, check other units from SpacePartitionComponent, but is pos(3,4) passable? UnitA has been moved to pos(3, 4), but SpacePartitionComponent has not been updated!


Br,
Chansey

[Michael Cann]

Well if you change the position of the unit which invalidates the SpacePartitionComponent then you need to update the SpacePartitionComponent in your NavigationSystem too! 

You can put a function in your SpacePartitionComponent that does the updating of the partition if you dont want to repeat yourself.

--

You received this message because you are subscribed to the Google Groups "Ash Framework" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ash-framewor...@googlegroups.com.
Visit this group at http://groups.google.com/group/ash-framework.
For more options, visit https://groups.google.com/d/optout.

[chan...@gmail.com]

@mikeysee

But it's very inconvenient, because it means all “moving-systems” (PhysicsSystem, FlyNavigationSystem, CrawlNavigationSystem, VehicleNavigationSystem, TeleportSystem, WanderSystem, etc) will depend on SpacePartitionComponent.

In concept “moving-systems” shouldn’t depend on SpacePartitionComponen, it should depen on PositionComponent. (SpacePartitionComponent only a optimization)

Br,
Chansey

[Richard]

Hi Chansey

How many systems use the space partition data?

Richard

[chan...@gmail.com]

Hi, Richard,

To be frank, a lot of systems will use space partition data.

"UnitAISystems" will check nearby enemies.

"AbilitySystems" (eg:TeleportSystem) maybe jump units position.

"NavigationSystems"/"PhysicsSystem"/"SteeringSystems" will check units' colliston.

What seems strange to me is why ash (or entity system) can't support message passing to handle component data change?
NB: ash has supported handling node's add/remove but can't support handle component data change!

One solution of this is:
Create a SpacePartitionSystem which handles node's add/remove/change and update SpacePartitionComponent related.

For instance:

Create a entity which represent an "unit's AI world" and add an UnitSpacePartitionComponent to it.

UnitSpacePartitionSystem will handle UnitPositionComponent's add/remove/change and update UnitSpacePartitionComponent.

Create a entity which represent an "navigation world" and add an NavSpacePartitionComponent to it.

NavSpacePartitionSystem will handle UnitPositionComponent and NavObstacleComponent's add/remove/change and update NavSpacePartitionComponent.

"UnitPositionComponent and NavObstacleComponent's change" means: the change of (x,y) in UnitPositionComponent and the change of radius in NavObstacleComponent.

This solution used message passing and it seems not recommanded in entity system.....


Another solution of this is not use message passing:

For instance:

void Update()
{
  //...

  //all unit ai system's update();
  TeleportSystem.Update(); //<--- change UnitPositionComponent and UnitSpacePartitionComponent manually.

  //before all navgation system update()
  UnitPositionToNavigationPositionSystem.Update(); //since UnitPositionComponent has been changed in TeleportSystem.Update(), so we need synchronous data in NavigationComponent and NavSpacePartitionComponent.

  //navgation systems update()
  CrawlNavigationSystem.Update() //process moving change NavPositionComponent and SpacePartitionComponent manually.
  VehicleNavigationSystem.Update() //process moving change NavPositionComponent and NavSpacePartitionComponent manually.

  //after all navgation systems update()
  UnitNavigationPositionToUnitPostionSystem.Update(); //synchronous data back!

  // all render system update()
  RenderSystem.Update() // which will use UnitPositionComponent.

}

Which solution is better?  Or better way?

Any advice would be very appreciated.

Thanks,

Br,
Chansey

在 2015年2月5日星期四 UTC+8上午4:11:52，Richard写道：

[Richard]

Entity systems don't ban message passing. I myself have advocated (elsewhere on this forum) placing event listeners inside components, with the strict proviso that they only be used to modify the data in that component. This follows on from the idea that I have also mentioned elsewhere of having functions inside the component to make setting the data in the component easier - these functions are only allowed to manipulate the data in the component.

I apologise if any of my code is wrong here, I haven't written any Actionscript for quite a while. I would suggest one of the following...

1. Use a flag in the position component to indicate if the position has changed. Use a system to recalculate the space partition for those that have changed. 

public class PositionComponent
{
 private var _position : Vector3D;
 public function get position() : Vector3D
 {
 return _position;
 }
 public function set position( value : Vector3D ) : void
 {
 _position = value;
 changed = true;
 }
 
 public var changed : Boolean;
}


public class SpacePartitionComponent
{
 // ...
}


public class SpacePartitionSystem extends System
{
 // ...
 override public function update( time : Number ) : void
 {
 for( node = nodes.head; node; node = node.next )
 {
 if( node.position.changed )
 {
 // recalculate space partition data in SpacePartitionComponent
 
 node.position.changed = false;
 }
 }
 }
}

2. Place the space partition data in the same component as the position data. Update the space partition data whenever the position changes.

public class PositionComponent
{
 private var _position : Vector3D;
 public function get position() : Vector3D
 {
 return _position;
 }
 public function set position( value : Vector3D ) : void
 {
 _position = value;
 // recalculate space partition here
 }
 
 public var spacePartition;
}

3. Place a signal in the position component. Dispatch the signal whenever the position changes. Listen for the signal in the space partition component and update it when the position changes.

public class PositionComponent
{
 private var _position : Vector3D;
 public function get position() : Vector3D
 {
 return _position;
 }
 public function set position( value : Vector3D ) : void
 {
 _position = value;
 changed.dispatch( value );
 }
 
 public var changed : Signal1 = new Signal1( Vector3D );
}


public class SpacePartitionComponent
{
 public var spacePartition;
 
 public function positionChanged( position : Vector3D ) : void
 {
 // recalculate space partition
 }
}


PositionComponent pc = new PositionComponent();
SpacePartitionComponent spc = new SpacePartitionComponent();
entity.add( pc );
entity.add( spc );
pc.changed.add( spc.positionChanged );

4. Treat the space partition class as a helper algorithm for systems, not as core game data. This is unconventional but valid on the basis that the spaced partition data is not core game data. It is just data that is calculated and cached to aid performance in some systems. If lost it can be recalculated from the core game data.

public class PositionComponent
{
 private var _position : Vector3D;
 public function get position() : Vector3D
 {
 return _position;
 }
 public function set position( value : Vector3D ) : void
 {
 _position = value;
 changed = true;
 }
 
 public var changed : Boolean;
}


public class SpacePartitioning
{
 public function update()
 {
 // update internal partitioning data based on which objects have changed position
 }
}


SpacePartitioning sp = new SpacePartitioning();
NavigationSystem = new NavigationSystem( sp );

I'm not a fan of options 1 or 4 because the changed property looks like a public property that any system could use but it can only actually be safely used by the space partition code because that code resets it to false after it has used it.

You could create option 4 but use signals instead, like in option 3, but it will be hard/expensive to fetch the entity from the position component each time the signal is dispatched and the space partition class probably needs to know which entity it is.

Richard

[chan...@gmail.com]

Hi Richard,

"Entity systems don't ban message passing."

Since some article said "Component mustn't have any code except getter/setter" .....

Very thanks for your clarification.

I will use option 4, and use SpacePartitioningSystem instead of helper class SpacePartitioning, because SpacePartitioningSystem could handle PositionComponent add/remove.

Br,
Chansey

在 2015年2月5日星期四 UTC+8下午6:16:27，Richard写道：

...