Forum Libraries, Components, and Plugins

Where is hit detection?

In looking at the monkey banana example code, I was surprised to see that CCNode hit detection was accomplished by iterating through every CCNode in the scene and manually checking for rectangle intersection. I thought one of the main points of CocosSharp was to provide a 2D scene graph and a scene graph, I thought, was to maintain a data structure of all nodes in such a way for incredibly fast hit detection performance. Therefore, I was expecting some method like, NodesAtPoint or NodesInRectangle on the scene or a layer.

Imagine if I wanted to write a pixel drawing app where every pixel was a CCNode. As I draw my finger over those pixels (CCNodes), they should all change color. I wrote the code for this in CocosSharp but I need a hit detection algorithm to detect which node is under my finger while drawing. If I iterate over every node in the scene to manually check rectangle intersection, I am wasting my time. In this specific case, all CCNodes are organized into a nice grid so it is trivial to find the exact single node at any point in the scene. However, I was expecting the CocosSharp scene graph to be this smart by how it maintains its data structure of nodes.

Anyway, I did my own trivial hit detection knowing that the nodes were arranged in a nice grid. I then cranked up the number of nodes by increasing the size of the grid. I created a 50x50 grid (2500 nodes) and performance was HORRIBLE! I will attempt to profile the app to see where the bottleneck lies, but I was expecting fantastic performance with only 2500 nodes since CocosSharp can handle particle systems without any problem.

I am a newbie at CocosSharp and game development in general so maybe my expectations are to high or I just wrote bad code. Any suggestions or corrections to my thinking are welcome. I have attached my source code.

using System;

using Xamarin.Forms;
using CocosSharp;
using System.Collections.Generic;

namespace MyGame.Pages
{
    public class GamePage : ContentPage
    {
        private const int NUM_ROWS = 50;
        private const int NUM_COLS = 50;
        private const int GAP = 2;

        private CocosSharpView _ccView = null;
        private CellNode[,] _cells = null;
        private bool _drawOn;

        public GamePage ()
        {
            _ccView = new CocosSharpView {
                VerticalOptions = LayoutOptions.FillAndExpand,
                ViewCreated = LoadGame
            };
            Label helloL = new Label {
                Text = "Hello CocosSharp Forms",
                HorizontalTextAlignment = TextAlignment.Center
            };
            Content = new StackLayout {
                Children = {
                    _ccView, helloL
                }
            };
        }

        private void LoadGame(object sender, EventArgs ea)
        {
            CCGameView gameV = sender as CCGameView;
            if (gameV != null) {
                gameV.DesignResolution = new CCSizeI ((int)_ccView.Width, (int)_ccView.Height);
                CCScene gameS = new CCScene (gameV);
                CCLayer gameL = new CCLayer();
                int cellWidth = ((int)_ccView.Width - (GAP * (NUM_COLS + 1))) / NUM_COLS;
                int cellHeight = ((int)_ccView.Height - (GAP * (NUM_ROWS + 1))) / NUM_ROWS;
                _cells = new CellNode[NUM_ROWS,NUM_COLS];
                for (int r = 0; r < NUM_ROWS; r++) {
                    for (int c = 0; c < NUM_COLS; c++) {
                        int cellX = (c * cellWidth) + ((c + 1) * GAP);
                        int cellY = (r * cellHeight) + ((r + 1) * GAP);
                        CellNode node = new CellNode ();
                        node.Size = new CCSize (cellWidth, cellHeight);
                        node.Position = new CCPoint (cellX, cellY);
                        node.IsOn = ((r % 2) == 0);
                        gameL.AddChild(node);
                        _cells[r,c] = node;
                    }
                }
                CCEventListenerTouchAllAtOnce tl = new CCEventListenerTouchAllAtOnce ();
                tl.OnTouchesBegan = OnTouchesBegan;
                tl.OnTouchesMoved = OnTouchesMoved;
                tl.OnTouchesEnded = OnTouchesEnded;
                gameL.AddEventListener (tl);
                gameS.AddLayer (gameL);
                gameV.RunWithScene (gameS);
            }
        }

        private CellNode HitCell(CCPoint layerPt)
        {
            int cellWidth = ((int)_ccView.Width - (GAP * (NUM_COLS + 1))) / NUM_COLS;
            int cellHeight = ((int)_ccView.Height - (GAP * (NUM_ROWS + 1))) / NUM_ROWS;
            float cellAndMarginWidth = cellWidth + GAP;
            float cellAndMarginHeight = cellHeight + GAP;
            int col = (int)(layerPt.X / cellAndMarginWidth);
            int row = (int)(layerPt.Y / cellAndMarginHeight);
            if ((row < 0) || (col < 0) || (row >= NUM_ROWS) || (col >= NUM_COLS))
                return(null);
            return(_cells [row, col]);
        }

        private void OnTouchesBegan (List<CCTouch> touches, CCEvent touchEvent)
        {
            CellNode cell = HitCell (touches [0].Location);
            if (cell == null)
                return;
            cell.IsOn = !cell.IsOn;
            _drawOn = cell.IsOn;
        }

        private void OnTouchesMoved (List<CCTouch> touches, CCEvent touchEvent)
        {
            CellNode cell = HitCell (touches [0].Location);
            if (cell == null)
                return;
            cell.IsOn = _drawOn;
        }

        private void OnTouchesEnded (List<CCTouch> touches, CCEvent touchEvent)
        {
            Console.WriteLine (touchEvent);
        }
    }

    class CellNode : CCDrawNode
    {
        public CCSize Size { get; set;}
        private bool _isOn;
        public bool IsOn {
            get { return(_isOn); }
            set {
                _isOn = value;
                Clear();
                CCColor4B c = (_isOn) ? CCColor4B.Blue : CCColor4B.White;
                DrawRect (new CCRect (0, 0, Size.Width, Size.Height), c);
            }
        }
    }
}

Best Answer

Answers

  • VictorChelaruVictorChelaru USMember ✭✭

    Hi Shawn,

    The scene graph that you mentioned is a hierarchy which helps organize children nodes for the purpose of positioning, scaling, rotating, controlling visibility, etc. As far as I know, the purpose of the scene graph is not to help improve the performance of picking (which is essentially collision).

    Looping through all objects to check for any kind of collision is what is often referred to as a "brute force" approach, and it works okay if you have a small number of objects. Once you start getting to a larger number of checks (like over 1000), then you need to implement some kind of smarter algorithm.

    What you've implemented, using the grid to help you identify what you're touching, is perfectly acceptable, and there's really no algorithm that can possibly get any faster than that. If your objects are arranged in a grid, this is the way to go.

    That said, I don't think using a single CCRect per pixel is how you should go about implementing a drawing app. If you're familiar with non-CocosSharp app development, it would be like coloring a screen by making thousands (millions?) of buttons, each 1x1 pixel. CCRects (and buttons) have too much overhead to be properly used at that scale.

    The approach I'd take is to create a render target which you can update as the user draws, and draw that with a single CCSprite. There aren't any Xamarin guides on how to use this class, but there is a little bit of info in the docs:

    http://developer.xamarin.com/api/type/CocosSharp.CCRenderTexture/

    Hope that helps!

  • ShawnCastrianniShawnCastrianni USBeta ✭✭✭

    Thanks for responding.

    My first point about the scene graph and the hit detection was that I was disappointed that I had to come up with the smarter algorithm myself and it wasn't built into CocosSharp. If CocosSharp has all of the physics engine and collision detection logic built in, where is it so that I can simply ask what nodes intersect a given point?

    I agree that a drawing app built this way is a bad idea. I was just using that as an example to illustrate kind of what I am trying to do without going into all of the details. I just need a grid of nodes or something that looks like a grid of nodes that responds to touch and toggles the nodes on or off. If the user drags his finger across the grid, all of the nodes turn on one by one as he drags, like a drawing app. I am trying to get this performant at a maximum of 50x50 nodes and that also allows pinch to zoom.

  • rene_ruppertrene_ruppert DEXamarin Team, University, XamUProfessors Xamurai

    If I interpret your question correctly, there is no need for any hit testing. You have an array of controls which are aligned in a grid. So you can go ahead and divide the current pointer location by the width and height of your cells. Round the resulting values down to the next integer. This will give you the column and the row of the touch. Now you just have to multiply the row with the number of columns in your grid and add the column to get the index of the touched node, which is stored in the array.

  • ShawnCastrianniShawnCastrianni USBeta ✭✭✭
    edited December 2015

    Yes, I know that. I have implemented that in the code I posted above in the method HitCell. My point is that why did I have to implement that algorithm myself? Why doesn't CocosSharp have an efficient algorithm built in? Why are we expected to loop through all nodes and ask if each one intersects a point? So I will repeat my question from above:

    If CocosSharp has all of the physics engine and collision detection logic built in, where is it so that I can simply ask what nodes intersect a given point?

    For example, with SpriteKit on iOS, I can simply call:

    SKNode node = skView.Scene.GetNodeAtPoint (scenePt);
    
  • ShawnCastrianniShawnCastrianni USBeta ✭✭✭
    edited December 2015

    And similarly, with SceneKit on iOS, I can simply call:

    NSArray nodes = SCNView.HitTest (scenePt, options);
    
  • VictorChelaruVictorChelaru USMember ✭✭

    Hi Shawn,

    The immediate answer is because whether you do something like brute force vs. grid-based vs. axis-based partitioning vs. quadtree vs. any other type of partitioning/algorithm depends on your arrangement of objects. I'd use axis-based partitioning if i was distributed among one axis, and if my objects didn't shuffle a lot. I might quadtree if I have a really large area that I needed to cover which wasn't primarily distributed on one axis.

    These distribution and behavioral characters can't automatically be interpreted by CocosSharp, it's something that requires a human brain. There's some algorithms which make assumptions about how things are laid out, or which require numerous coefficients to work efficiently (like how big cell sizes should be in a quad tree). You'll never get a function like PerformTheBestAlgorithmForMe().

    That said, CocosSharp could provide a number of common collision data structures/algorithms, and it may in the future. Until then, this falls into the category of problems which requires a custom solution at scale.

Sign In or Register to comment.