How to write a script to make npc determine which seat is empty and go sit on it?

Hi, I am sorry that I am not a native English speaker, so I apologize for my poor grammar.
If someone can give me advice, I will be grateful!

Here is my need:
I am making a game that is based on a subway theme, NPC will be instantiated at the car door. In this game, NPC should know which seat in the car is empty and which seat is sat by another NPC, so 2 NPC won’t bump into each other in the same seat. I hope all seats can be applied with same script, because the current method I used is that I give every seat its own script with its own bool (A seat with a bool A, B seat with a bool B…and so on) and NPC will read all over the bools and decide where it should go. But this method is unreasonable when the number of the seat is increasing. I think this logic may be also apply to a restuarant game but I don’t know how to write it.

Thanks to anyone who reply to the question.

You need a slot collection. I’ll assume you want to know exactly which NPC is sitting where, identified by some integer.

A slot manager is a collection in memory that has a fixed amount of items that can change their state. In theory no two slots should share the same state (unless it’s 0; Edit: in my case it’s a special value of EMPTY), but I’ll ignore that constraint for the sake of simplicity.

You want a couple of features to make this useful, let’s start from the most basic ones first.
First you need an array to represent your seats.

using System;
using System.Collections.Generic;
using UnityEngine;

public class SeatCollection {

  public const int EMPTY = -1;

  int[] _seats;
  int _occupied;

  public SeatCollection(int seatCount) {
    _seats = new int[seatCount];
    Array.Fill(_seats, EMPTY, 0, seatCount); // fill in the 'empty' values
    _occupied = 0;
  }

}

First we want this basic check in place, this helps with the logic.

// returns true if the seat is vacant, false if not
public bool IsVacant(int seatIndex)
  => _seats[seatIndex] == EMPTY;

Then you want to introduce the means of reading and manipulating the slots.

public int SeatContent(int seatIndex)
  => _seats[seatIndex];

// returns false if the seat was already occupied, we don't want the occupant to 'perish'
public bool TryAssignSeat(int seatIndex, int npcId) {
  if(npcId < 0) throw new ArgumentException("NPC id cannot be a negative number.");
  if(!IsVacant(seatIndex)) return false;
  _seats[seatIndex] = npcId;
  _occupied++;
  return true;
}

Then you want some helpers to allow you to abstract the collection further. And also to allow for basic ‘unseating’.

// returns EMPTY if seat wasn't occupied, otherwise returns id of unseated NPC
public int Unseat(int seatIndex) {
  if(!IsVacant(seatIndex)) {
    var npcId = _seat[seatIndex];
    _seats[seatIndex] = EMPTY;
    _occupied--;
    return npcId;
  }
  return EMPTY;
}

// this is the less smart way to do this
// public bool TryAssignRandomSeat(int npcId)
//  => TryAssignSeat(Random.Range(0, _seats.Length), npcId);

Then something to help you query the seats.

public int TotalSeats => _seats.Length;
public int OccupiedSeats => _occupied;
public int VacantSeats => TotalSeats - OccupiedSeats;

// this would be a smarter way to do random seating
public bool TryAssignRandomSeat(int npcId) {
  if(VacantSeats == 0) return false; // this is critical because we know there's no space
  // there are ways to make this more optimal, but will work just fine for small seat counts
  while(!TryAssignSeat(Random.Range(0, _seats.Length), npcId)) {}
  return true;
}

// returns the seat index of specified NPC, or EMPTY if it wasn't found
public int SeatOf(int npcId) {
  int found = EMPTY;
  for(int i = 0; i < _seats.Length; i++)
    if(_seats[i] == npcId) { found = i; break; }
  return found;
}

// returns true if the specified NPC was seated, false if not
public bool IsSeated(int npcId)
  => SeatOf(npcId) != EMPTY;

Then something to help you iterate through the seated NPCs.

// returns the seated NPCs, one by one in a foreach clause
IEnumerator<int> SeatedNPCs() {
  for(int i = 0; i < _seats.Length; i++)
    if(!IsVacant(i)) yield return _seats[i];
}

// returns the occupied seats, one by one in a foreach clause
IEnumerator<int> OccupiedSeats() {
  for(int i = 0; i < _seats.Length; i++)
    if(!IsVacant(i)) yield return i;
}

// unseats everyone and returns an array containing 'everyone'
public int[] UnseatEveryone() {
  var result = new int[_occupied];
  int index = 0;
  for(int i = 0; i < _seats.Length; i++) {
    if(!IsVacant(i)) {
      result[index++] = _seats[i];
      _seats[i] = EMPTY;
    }
  }
  _occupied = 0;
  return result;
}

This is how you can use this

var mySchoolBus = new SeatCollection(24);

mySchoolBus.TryAssignRandomSeat(npc1);
mySchoolBus.TryAssignRandomSeat(npc2);

Debug.Log(mySchoolBus.IsSeated(npc3));
Debug.Log(mySchoolBus.IsSeated(npc2));
Debug.Log(mySchoolBus.SeatOf(npc2));

foreach(var npc in mySchoolBus.SeatedNPCs()) {
  Debug.Log(npc);
}

foreach(var seat in mySchoolBus.OccupiedSeats()) {
  Debug.Log(seat);
}

Debug.Log(mySchoolBus.SeatContent(1) == SeatCollection.EMPTY);

mySchoolBus.Unseat(mySchoolBus.SeatOf(npc1));
mySchoolBus.TryAssignRandomSeat(npc3);

var unseated = mySchoolBus.UnseatEveryone();
Debug.Log(unseated.Length);

NOTE: If something doesn’t work, it’s probably a typo. Please let me know and I’ll fix it.
Also keep in mind I’m likely to edit this a couple of times more, so make sure to refresh the page from time to time.

Edit:
Changed all occurrences of _seats.Count → _seats.Length, that was a major typo on my part.

1 Like

Here are a couple of more advanced methods you can also have, like adding or removing multiples of NPCs

// this will return how many npcs were successfully seated
public int TryAssignRandomSeat(params int[] npcs) {
  if(npcs is null) throw new ArgumentNullException();
  if(npcs.Length == 0) return 0; // basically nothing happens
  var success = 0;
  for(int i = 0; i < npcs.Length; i++)
    if(TryAssignRandomSeat(npcs[i])) success++; else break;
  return success;
}

// this one differs from Unseat in that it can unseat a particular npc
// returns true on success, false on failure (such npc wasn't seated)
public bool UnseatNPC(int npcId) {
  var seatIndex = SeatOf(npcId); // SeatOf will return EMPTY on failure
  if(seatIndex == EMPTY) return false;
  Unseat(seatIndex);
  return true;
}

// we can now unseat multiple NPCs
public void UnseatNPCs(params int[] npcs) {
  if(npcs is null) throw new ArgumentNullException();
  for(int i = 0; i < npcs.Length; i++)
    UnseatNPC(npcs[i]);
}

Now you can write the following code

mySchoolBus.TryAssignRandomSeat(michael, jenny, tom);
mySchoolBus.UnseatNPCs(tom, jenny);

// you can also pass in an array
var myNPCs = new int[] { 5, 11, 22 };
mySchoolBus.TryAssignRandomSeat(myNPCs);

You can also support lists instead of arrays, but I’m sure I’ll make a mistake writing this from my head, so let’s go without it. But once you have everything in place, it’s very easy to enlarge the business of this collection in multiple directions.

I am really bothered with how TryAssignRandomSeat works, so let’s do this even smarter

// this would be the smartest way to do random seating
public bool TryAssignRandomSeat(int npcId) {
  if(npcId < 0) throw new ArgumentException("NPC id cannot be a negative number.");

  var vac = VacantSeats;
  if(vac == 0) return false; // this is critical because we know there's no space
 
  var rn = Random.Range(0, vac);
  var index = -1;
  for(int i = 0; i < _seats.Length; i++) {
    if(IsVacant(i)) {
      if(++index == rn) {
        _seats[i] = npcId;
        _occupied++;
        return true;
      }
    }
  }

  Debug.Assert(false, "Code should never reach here");
  return false;
}

We can also play more with this, and introduce predicates, if you want to be sure that only the seats next to the window will be selected, or only seats in front of the bus etc. Obviously this depends on how you physically allocate the seat indices, but we can at least exert some control over the assignment process.

// the second argument is optional (see below for usage)
public bool TryAssignRandomSeat(int npcId, Func<int, bool> predicate = null) {
  if(npcId < 0) throw new ArgumentException("NPC id cannot be a negative number.");
  var vacancies = VacantSeats; // let's cache this because it's going to be used a lot

  if(vacancies == 0) return false;
  var randomInt = Random.Range(0, vacancies);

  var seats = _seats.Length;
  var seatCounter = -1, vacancyCounter = -1;
  var safetyMargin = 3 * seats;
  var success = false;

  while(!success) {
    if(++seatCounter == safetyMargin) break;

    var seatIndex = seatCounter % seats;

    if(IsVacant(seatIndex)) {
      if(predicate is null || predicate(seatIndex)) {
        if(++vacancyCounter == vacancies) vacancyCounter = 0;
        if(vacancyCounter == randomInt) {
          _seats[seatIndex] = npcId;
          _occupied++;
          success = true;
        }
      }
    }

  }

  return success; // should always be true unless predicate was horribly restrictive
}

Now you can use a lambda function to set a constraint, perhaps you want to allow only seats whose index is < 10?

mySchoolBus.TryAssignRandomSeat(jenny, i => i < 10 );

Or you want just the odd seats to be preferred?

mySchoolBus.TryAssignRandomSeat(jenny, i => i & 1 != 0 );

Etc.
IMPORTANT: Hopefully I didn’t make any mistakes with the code.
Because if I did, it’ll likely hang Unity in an endless loop. So be careful, save your work before you try it. And let me know.

Edit:
fixed a small typo
Edit2:
shuffled a little the predicate variant, after noticing problems with distribution
Edit3:
fixed a small oversight where index would grow larger than random value
Edit4:
another typo, sorry about that, but that’s what you get when you use forum edit as an IDE
Edit5:
and I forgot to update _occupied as well; also changed the var names to make it more readable
Edit6:
added back the error checking, because we don’t rely on the base method any more

1 Like

Now, the most of the things showed here are O(n) that means it’ll become more and more slow the more seats there are. So this isn’t supposed to be used on seat collections larger than, say 64 slots.

It also doesn’t prevent duplicate NPCs. In theory, setting the same NPC twice, should automatically remove the first instance (or at least warn you about duplication).

Both of these things can be solved with the use of an additional Dictionary, but there is too much to explain and you’ll be lost probably, so it’s out of scope of this crash course.

Duplication itself is very easy to solve with HashSet, but once we get that done it makes zero sense not to implement everything else properly with a Dictionary, like removing NPCs in O(1) time, but also finding their seats in O(1) time.

In any case, this is all just for posterity, I’m sure you’ll be fine with the code as it is.

1 Like

I only just now noticed that all ‘new’ keywords are automatically clickable. This was not intended by me!
Such a weird functionality.

1 Like