Jump to content

  • Log In with Google      Sign In   
  • Create Account


How to deal with Input Sequences?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 Danicco   Members   -  Reputation: 449

Like
0Likes
Like

Posted 23 February 2014 - 03:21 PM

I'm coding the Input part of an engine and this is the "flow" of command:

 

1. (Startup) GameCode defines Commands such as MOVE_LEFT, MOVE_RIGHT

- This command is saved in a vector _commandList

 

2. OS sets the values via the Input class by passing an Input ID and Value

- This changes depending on the OS, so the programmer just have to call the input methods to set values to keys

 

3. Whenever the OS sets a new value by Input ID, the Input checks if there's a command assigned to it, if there is, it adds a new element in a vector specifying everything

- This is where the issue is, I'm using new everytime

 

4. During the Game Loop, before the Update(), I check all values in this vector (InputQueue) and update the _commandList current state.

- After this the Update() loop will have a list of all commands and their state during that time

 

It's working fine for key presses and such, since there's only a few commands to each game. But now I added the movement X/Y input code and the InputQueue vector is growning HUGE when I move the mouse.

In the Input Update function I do remove inputs after a time, but I'm worried that when I move the mouse, on Windows, I get a message for every pixel I moved the mouse to.

So if I move the mouse 10 pixels left, I get 10 messages and that's 10 new inputQueues, 10 new checks, and 10 new deletes... if it's half a 1920 screen, that's 1000 news and deletes and I that seems worrisome...

 

So I'd like to remove this new/delete in this function since it's called thousands of time per second so I was thinking in moving to an array of fixed size, but then there's the cons of iterating over all elements in the array instead of a dynamic vector one, and that I don't know how to deal with moving elements in the array.

 

This is how it is currently:

vector<Command*> _commandList; //commands that will be defined per game
vector<InputQueue*> _inputQueue; //vector to hold all input to be processed in the next UPDATE
InputKeys _inputKeys[300]; //each one of these has 3 float values

//function when any input from the OS comes to the engine
void Input::SetInput(int inputCode, float valueX, float valueY, float valueZ)
{
    //Defining the inputKey values
    inputKeys[inputCode].valueX = valueX;
    inputKeys[inputCode].valueY = valueY;
    inputKeys[inputCode].valueZ = valueZ;

    //If there's a game command assigned to this input
    //Add a new input to the queue to be processed in the next main Update()
    if(inputKeys[inputCode].command != 0)
    {
        InputQueue* newInput = new InputQueue();
        newInput->valueX = inputKeys[inputCode].valueX;
        newInput->valueY = inputKeys[inputCode].valueY;
        newInput->valueZ = inputKeys[inputCode].valueZ;
        newInput->command = inputKeys[inputCode].command;
        newInput->time = timeModule.GetRealTime();

        _inputQueue.Add(newInput);
    }
}

//function called right before the main GAME CODE update
//I update all the game commands' states so the GAME CODE can use them
void Input::Update(uint64 currentTime)
{
    for(uint i = 0; i < _inputQueue.size(); i++)
    {
        if(_inputQueue[i]->time <= currentTime - inputTimeOnQueue)
        {
            delete _inputQueue[i];
            _inputQueue.erase(_inputQueue.begin() + i, _inputQueue.begin() + i + 1);
            i--;
            continue;
        }

        if(_inputQueue[i]->inputTime >= _lastUpdate && _inputQueue[i]->inputTime <= currentTime)
        {
            Command* command = _inputQueue[i]->command;
            //update the command state
            command->valueX = _inputQueue[i]->valueX;
            //etc
        }
    }
    _lastUpdate = currentTime;
}

After this, during the main Update I can check the _commandList values and they'll be updated ready for checking.

I'd like to change it to something like this:

vector<Command*> _commandList; //commands that will be defined per game
InputQueue _inputQueue[20]; //I set a maximum of 20 input queues per update - anymore and I'll erase the older ones
InputKeys _inputKeys[300]; //each one of these has 3 float values

//function when any input from the OS comes to the engine
void Input::SetInput(int inputCode, float valueX, float valueY, float valueZ)
{
    //Defining the inputKey values
    inputKeys[inputCode].valueX = valueX;
    inputKeys[inputCode].valueY = valueY;
    inputKeys[inputCode].valueZ = valueZ;

    //If there's a game command assigned to this input
    //Add a new input to the queue to be processed in the next main Update()
    if(inputKeys[inputCode].command != 0)
    {
        //I need to figure how to get this ? - probably an int and I'll check if it's 20 or > and reset to 0 if is
        _inputQueue[?]->valueX = inputKeys[inputCode].valueX;
        //etc
    }
}

//function called right before the main GAME CODE update
//I update all the game commands' states so the GAME CODE can use them
void Input::Update(uint64 currentTime)
{
    for(uint i = 0; i < 20; i++)
    {
        if(_inputQueue[i].time <= currentTime - inputTimeOnQueue)
        {
            //need to figure how to check current to last, considering the current might be 0~20
            //and break so I don't loop through all 20 when it's not needed (not sure if I need to worry about this)
        }

        if(_inputQueue[i].inputTime >= _lastUpdate && _inputQueue[i].inputTime <= currentTime)
        {
            Command* command = _inputQueue[i].command;
            //update the command state
            command->valueX = _inputQueue[i].valueX;
            //etc
        }
    }
    _lastUpdate = currentTime;
}

Any suggestions on how can I get this to work or any other way to handle this?



Sponsor:

#2 ultramailman   Prime Members   -  Reputation: 1558

Like
0Likes
Like

Posted 24 February 2014 - 01:58 AM

This looks quite confusing. Your InputQueue type is not a queue at all. It should be named input.

 

Also, no need to use new and delete if you are using a vector. Make your _inputQueue a vector<Input> instead of vector<Input*>

 

Actually, the way you use _inputQueue isn't queue-like at all. You might want to try switching to queue<Input>.


Edited by ultramailman, 24 February 2014 - 02:03 AM.


#3 haegarr   Crossbones+   -  Reputation: 3779

Like
0Likes
Like

Posted 24 February 2014 - 03:00 AM

Mice have a rate at which their state is sampled. I know of gaming mice with rates up to 1000 Hz (perhaps more is possible). However, many posts on the internet speak of problems at such a high rate and that such a high rate has no real life advantage, so usually you'll find advices to use 500 Hz. You don't get an input event per pixel from the OS; you get at most one event per sample. So "thousands of events per second" seems me way too many.

 

You can process mouse movement input before sending it to the game loop if you worry. Use the input event's timestamp to detect whether mouse movement samples come in too fast, and merge the 2nd event with the 1st one. This flattens the movement a bit, but it will not be important at such high rates. Of course, you must not exaggerate with lowering the result rate.

 

Avoiding calling new and delete can simply be done by using a pool allocator, so that obsoleted event objects are not deleted but stored in the pool, and new objects are not created but fetched from the pool. Creating a new object from scratch is then only needed if the pool is empty when fetching, and deletion can be implemented so that it is done only if the pool's pre-defined capacity is exhausted.



#4 Danicco   Members   -  Reputation: 449

Like
0Likes
Like

Posted 24 February 2014 - 03:31 PM


This looks quite confusing. Your InputQueue type is not a queue at all. It should be named input.

 

I already have an Input class.

My code (example) process Update() once every second.

But regardless of Update(), all inputs are passed to Input (could be more than one per second), which then orders the relevant ones into my InputQueue, which will be emptied/processed during the next Update().

 

 

 


Also, no need to use new and delete if you are using a vector. Make your _inputQueue a vector instead of vector

 

 

But then it would be the same as using an array and rearranging elements when I insert/remove one. I don't know how vectors do and it's probably better than any implementation I could think of, but it's something I want to avoid since it can affect the performance.

 

 

 


You can process mouse movement input before sending it to the game loop if you worry.

 

I'm trying to avoid "specific" inputs in the game code, somehow I managed to get this class working and it doesn't really know where/how the inputs come from, it just receives them and queue for the game code. I'd like to leave it like this so the game engine code doesn't care about how inputs come or what they are at all, and leaves it to the game code to send the messages (aiming for multi-platform engine).

 

 

 


Avoiding calling new and delete can simply be done by using a pool allocator, so that obsoleted event objects are not deleted but stored in the pool, and new objects are not created but fetched from the pool.

 

I think that's what I'm going to try to implement then, I've read about it once but I thought it was too complex/over engineering things and I left it aside, but it seems it fits nicely for the problem. Thank you for the suggestion!


Edited by Danicco, 24 February 2014 - 03:32 PM.


#5 ultramailman   Prime Members   -  Reputation: 1558

Like
1Likes
Like

Posted 24 February 2014 - 04:51 PM

So what exactly is your InputQueue type? Is it a queue?

From this snippet here

 

 


InputQueue* newInput = new InputQueue();

newInput->valueX = inputKeys[inputCode].valueX;

newInput->valueY = inputKeys[inputCode].valueY;

newInput->valueZ = inputKeys[inputCode].valueZ;

newInput->command = inputKeys[inputCode].command;

newInput->time = timeModule.GetRealTime();

 

I'm lead to believe your InputQueue object is not a queue, but an object that stores some input state for a particular input event.


Edited by ultramailman, 24 February 2014 - 05:03 PM.


#6 Danicco   Members   -  Reputation: 449

Like
0Likes
Like

Posted 24 February 2014 - 05:48 PM


So what exactly is your InputQueue type? Is it a queue?

 

The InputQueue type is an object that holds information on an Input to be processed later.

 


I'm lead to believe your InputQueue object is not a queue, but an object that stores some input state for a particular input event.

 

It's not the queue (the vector _inputQueue is), but I don't really go naming classes like InputInTheQueue...

Hmm although it could be InputQueued or something like that...



#7 dejaime   Crossbones+   -  Reputation: 3739

Like
0Likes
Like

Posted 24 February 2014 - 06:29 PM

You could also sample the mouse position on a per-frame basis. Keep the old position stored and update the new one every frame.

Even though I don't know what you are using to detect the input, there are libraries that you can poll your mouse position. I myself always encapsulate the mouse behind a MouseController: public Controller or something like that...



#8 ultramailman   Prime Members   -  Reputation: 1558

Like
0Likes
Like

Posted 24 February 2014 - 06:43 PM


The InputQueue type is an object that holds information on an Input to be processed later.

Haha, there we go. A common name for that kind of object is InputEvent or InputState. Please, don't name it queue if it is not a first in first out (FIFO) data structure , people are going to read your code and get confused. :)

 

 

I'm still a little confused on the Update function though.

for(uint i = 0; i < _inputQueue.size(); i++)
{
    if(_inputQueue[i]->time <= currentTime - inputTimeOnQueue)
    {
        delete _inputQueue[i];
        _inputQueue.erase(_inputQueue.begin() + i, _inputQueue.begin() + i + 1);
        i--;
        continue;
    }

 

Why do you remove some item, but not the others?

 

But let's say you have a very good reason for that. The way you remove it is std::vector.erase, an O(n) operation because of the array left shift. If you want to remove stuff from the middle, you will want to switch to a std::list data structure instead, since it supports O(1) removal of items.

 

I still recommend std::queue though, seeing how your _inputQueue is supposed to be a queue :\



#9 SunDog   Members   -  Reputation: 232

Like
0Likes
Like

Posted 24 February 2014 - 06:46 PM

You could also sample the mouse position on a per-frame basis. Keep the old position stored and update the new one every frame.

Even though I don't know what you are using to detect the input, there are libraries that you can poll your mouse position. I myself always encapsulate the mouse behind a MouseController: public Controller or something like that...

 

Yes this is one option.   For an FPS, this might be OK.    However if you have a mouse cursor thats independent of the display (like what happens in an RTS) if the frame rate slow down, theres not a good reason why the cursor should lag behind the rest of the frame.  One way to handle this problem is have the UI be an entirely seperate thread from the rest of the game engine.

 

But if you are talking about whats affecting your 3D rendering, it does probably make sense, in any case, to deal that way with mouse clicks (user actions).

 

Also, yes a queue is the name for a formal data structure.  It (should) imply a first-in-first-out (FIFO) interaction.   The C++ STL somewhat abuses this definition with their deque (double-ended queue) template, in which you can remove/add elements to both the front and back of the list.   I think they did it that way to avoid having to write a seperate stack strucutre - the deque can easily be used as a stack as well as  FIFO queue.


Edited by SunDog, 24 February 2014 - 06:51 PM.


#10 dejaime   Crossbones+   -  Reputation: 3739

Like
0Likes
Like

Posted 24 February 2014 - 06:54 PM

However if you have a mouse cursor thats independent of the display (like what happens in an RTS) if the frame rate slow down, theres not a good reason why the cursor should lag behind the rest of the frame.

But if the frame rate slows down, usually the mouse will be rendered at that same slow frame rate. I see no advantages on keeping the mouse refreshing while the user can't see where it is at.

#11 Danicco   Members   -  Reputation: 449

Like
0Likes
Like

Posted 24 February 2014 - 07:15 PM


Why do you remove some item, but not the others?

 

The vector is also supposed to keep the "history" of relevant inputs, so the game code could call:

if(input.IsMatch("MOVE_DOWN", "MOVE_DOWN_LEFT", "MOVE_LEFT"))
{
   //Do something knowing this sequence has been pressed, such as a special move for fighting games
}

So I check if it's time to remove the input from the history or not, and process the ones for the next update (because my code might've lagged out, so I'm only queueing the ones in between a certain time frame).

 

And well, regarding the names, it's still a queue... it's just not the std::queue.

When I think queue, I think "ah, something that will be dealt with later on" (and when the order is important). And also I never knew about the std::queue before this topic ahahaha

Though it wouldn't fit in this example since the vector is doing more than just a queue.



#12 SunDog   Members   -  Reputation: 232

Like
0Likes
Like

Posted 24 February 2014 - 07:55 PM


 

However if you have a mouse cursor thats independent of the display (like what happens in an RTS) if the frame rate slow down, theres not a good reason why the cursor should lag behind the rest of the frame.

But if the frame rate slows down, usually the mouse will be rendered at that same slow frame rate. I see no advantages on keeping the mouse refreshing while the user can't see where it is at.

 

 

Isn't it possible to have the mouse be drawn over the scene, even if the scene isn't completed rendering yet? 

 

This would involve moving the SwapBuffers or whatever the equivalent is outside of the rendering loop, but I think it should be possible.  



#13 ferrous   Members   -  Reputation: 1604

Like
0Likes
Like

Posted 24 February 2014 - 08:11 PM

Sounds like people are getting hung up on your input queue. =)

 

As someone else mentioned, lowering the rate at which you sample the mouse would probably help.

 

And as the OP mentioned, instead of doing a new/delete, moving that to non-dynamic memory would help as well.  One way to do it would be to move to a memory pool.  Though unless you did the reduced mouse sampling, all this would do is push out all the other samples.  (or put the mouse sampling in it's own pool, so you have all the possible keyboard/button inputs, and then like the last 30 mouse moves)

 

EDIT:

 

A crap example of a memory pool:

MAX_INPUTS=32

Queue<int> m_InputQueue;  // holds indices into the array of input samples

InputEvent  m_inputEvents[MAX_INPUTS];

int inputmapping; //each bit represents an index, if the bit is set, the index is in use


Edited by ferrous, 24 February 2014 - 08:14 PM.


#14 dejaime   Crossbones+   -  Reputation: 3739

Like
0Likes
Like

Posted 24 February 2014 - 08:32 PM

Isn't it possible to have the mouse be drawn over the scene, even if the scene isn't completed rendering yet? 
 
This would involve moving the SwapBuffers or whatever the equivalent is outside of the rendering loop, but I think it should be possible.

Possible, it is. Still, when you update the UI, with the "game layer" frozen, your cursor would leave a "clone trail" behind it. Even if this is done, I don't see how it would be of use. It would probably make frame rate drops worse.

Edited by dejaime, 24 February 2014 - 08:34 PM.


#15 ultramailman   Prime Members   -  Reputation: 1558

Like
0Likes
Like

Posted 24 February 2014 - 10:31 PM


The vector is also supposed to keep the "history" of relevant inputs, so the game code could call:

if(input.IsMatch("MOVE_DOWN", "MOVE_DOWN_LEFT", "MOVE_LEFT"))
{
//Do something knowing this sequence has been pressed, such as a special move for fighting games
}

So I check if it's time to remove the input from the history or not, and process the ones for the next update (because my code might've lagged out, so I'm only queueing the ones in between a certain time frame).



And well, regarding the names, it's still a queue... it's just not the std::queue.

When I think queue, I think "ah, something that will be dealt with later on" (and when the order is important). And also I never knew about the std::queue before this topic ahahaha

Though it wouldn't fit in this example since the vector is doing more than just a queue.

 

Ahh I get you. In that case, std::list should be perfect for this job, because of the O(1) removal of items. In theory, std::vector's erase is relatively slow near the beginning of the vector because you have a whole array to shift to the left. In practice though, you'll be fine until you notice significant slowdown caused by the vector.

 

Indeed, I was too hung up on the queue.



#16 ferrous   Members   -  Reputation: 1604

Like
0Likes
Like

Posted 25 February 2014 - 02:31 PM

 

Isn't it possible to have the mouse be drawn over the scene, even if the scene isn't completed rendering yet? 
 
This would involve moving the SwapBuffers or whatever the equivalent is outside of the rendering loop, but I think it should be possible.

Possible, it is. Still, when you update the UI, with the "game layer" frozen, your cursor would leave a "clone trail" behind it. Even if this is done, I don't see how it would be of use. It would probably make frame rate drops worse.

 

 

For those concerned about the mouse graphically, look into Hardware Mouse Cursor






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS