手写简单策略版游戏匹配算法

前言

游戏一般分为房间场和匹配场，现实中游戏匹配的算法需要考虑的因素比较多。笔者只是纯粹娱乐，分析一下一个简单的游戏匹配。
假设场景是简单的LOL玩家匹配
1.当玩家数量达到一定规定最小数时匹配，比如最小玩家匹配数是2吧
2.有时候玩家匹配的数量不确定，比如匹配是只要小于最大玩家数，比如3个玩家也可以玩游戏
总结上面，匹配到2或3个人数时，开始游戏

整体设计

整个匹配分为两个阶段

1. 第一阶段match：一直等到满足最低人数要求，然后进入第二阶段match2
2. 第二阶段match2：额外等待一段时间，然后创建房间
   所以需要的属性至少得包括房间最小人数、房间最小人数额外等的人的数量、额外需要等待的秒数、游戏类型的名称、玩家队列、匹配日志

     /**
        * 是否显示匹配日志：显示(true), 不显示(false)
        */
       private static final boolean SHOW_MATCH_LOG = true;
       
       /**
        * 房间最小人数
        */
       private static final int ROOM_MIN_NUM = 2;
       
       /**
        * 房间最小人数额外等的人的数量
        */
       private static final int ROOM_ADDITION_NUM = 1;
       
       /**
        * 额外需要等待的秒数
        */
       private static final int ROOM_ADDITION_SECOND = 5;
       
       
       /**
        * 游戏类型的名称
        */
       private static final Map<Integer, String> GAME_TYPE_NAME = new HashMap<Integer, String>()
       {
           {
               put(0, "匹配自选模式");
               put(1, "极地大乱斗");
               put(2, "单双排");
               put(3, "灵活排位");
               put(4, "无线火力");
               put(5, "镜像模式");
           }
       };
       
       /**
        * 玩家队列
        */
       private static final Map<Integer, List<BaseUser>> PLAYER_QUEUE = new ConcurrentHashMap<Integer, List<BaseUser>>()
       {
           {
               put(0, new ArrayList<>());
               put(1, new ArrayList<>());
               put(2, new ArrayList<>());
               put(3, new ArrayList<>());
               put(4, new ArrayList<>());
               put(5, new ArrayList<>());
           }
       };
   
   
       public class BaseUser {
       private int id ;
   
       private String name;
   
       public BaseUser(int id, String name) {
           this.id = id;
           this.name = name;
       }
   
       public int getId() {
           return id;
       }
   
       public void setId(int id) {
           this.id = id;
       }
   
       public String getName() {
           return name;
       }
   
       public void setName(String name) {
           this.name = name;
       }
   }

玩家匹配加入

当玩家点击开始匹配时，将玩家加入对应的游戏中的玩家队列中

/**
  * 将玩家加入匹配
  *
  * @param user 进行匹配的玩家
  * @param type 房间类型：
  * @return 操作成功(true), 操作失败(false)
  */
 public static boolean put(BaseUser user, int type) {
     add(user, type);
     System.out.println("startMatch");
     return true;
 }

  /**
  * 向匹配池添加玩家
  *
  * @param user 进行匹配的玩家
  * @param type 需要匹配的类型
  * @return 操作成功(true), 操作失败(false)
  */
 private synchronized static boolean add(BaseUser user, int type) {
     if (!PLAYER_QUEUE.containsKey(type)) {
         PLAYER_QUEUE.put(type, new ArrayList<>());
     }
     List<BaseUser> playerQueue = PLAYER_QUEUE.computeIfAbsent(type, k -> new ArrayList<>());
     if (!playerQueue.contains(user)) {
         playerQueue.add(user);
     }
     return true;
 }

匹配第一阶段

先用最简单的方式，这里简化了（应该用while（true）控制，匹配线程一直处于监听状态。
核心思想就是遍历玩家队列，如果规定指定人数开局，那么就不需要下一阶段，直接创建房间，队列中踢出玩家即可。

  /**
    * 匹配第一阶段
    */
   private static void match() {
           try {

               synchronized (PLAYER_QUEUE) {
                   PLAYER_QUEUE.forEach((type, userList) -> {
                       if (ROOM_MIN_NUM > 0 && userList.size() >= ROOM_MIN_NUM) {
                           // 已达到最低可开局人数，还需要额外等一会儿
                           scheduledExecutorService.schedule(() -> match2(type), 0, TimeUnit.SECONDS);           
                       }
                   });
                   if (SHOW_MATCH_LOG) {
                       testLog();
                   }
               }
               Thread.sleep(1000);
           }
           catch (InterruptedException e) {
               log.error(e.getMessage());
           }
   }


/**
    * 线程池
    */
   public static ScheduledExecutorService scheduledExecutorService =
       Executors.newScheduledThreadPool(Runtime.getRuntime().availableProcessors() * 2);
   


   public static void sleepSomeMillis(long millis) {
       try {
           Thread.sleep(millis);
       }
       catch (InterruptedException e) {
           log.error("睡眠等待时出现错误：" + e.getMessage());
       }
   }
   
   /**
    * 匹配日志
    */
   private static void testLog() {
       PLAYER_QUEUE.forEach((type, userList) -> {
           if (userList.size() > 0) {
               System.out.println(GAME_TYPE_NAME.get(type) + "人数为：" + userList.size());
           }
       });
   }

匹配第二阶段

该阶段主要考虑的因素包括等待额外的时间，以及玩家队列是否有人取消匹配导致不满足最小匹配人数等等，然后去匹配，
用线程池去控制匹配第二阶段

/**
  * 匹配第二阶段
  *
  * @param type 房间类型
  */
 private static void match2(int type) {
     List<BaseUser> users = PLAYER_QUEUE.get(type);
     long deadline = System.currentTimeMillis() + ROOM_ADDITION_SECOND * 1000;
     // 需要的最大的人数
     int realNeedNum = ROOM_MIN_NUM + ROOM_ADDITION_NUM;
     while (true) {
         if (System.currentTimeMillis() > deadline) {
             break;
         }
         synchronized (PLAYER_QUEUE) {
             if (users.size() < ROOM_MIN_NUM) {
                 return;
             }
             if (users.size() >= realNeedNum) {
                 break;
             }
         }
         sleepSomeMillis(500);
     }
     synchronized (PLAYER_QUEUE) {
         // 等待结束之后实际的人数
         int realNum = users.size() > realNeedNum ? realNeedNum : users.size();
         // 如果人数仍然满足最小匹配人数，则创建房间
         if (realNum >= ROOM_MIN_NUM) {
             createRoom(type, realNum);
         }
     }
 }

创建房间

该阶段显示在玩家队列中踢出已匹配的玩家，然后在创建房间

/**
 * 创建房间
 *
 * @param type 房间类型
 * @param playerNum 房间人数
 */
private static void createRoom(int type, int playerNum) {
    synchronized (PLAYER_QUEUE) {
        BaseUser[] baseUsers = new BaseUser[playerNum];
        List<BaseUser> users = PLAYER_QUEUE.get(type);
        if (users.size() >= playerNum) {
            for (int i = 0; i < playerNum; i++) {
                baseUsers[i] = users.get(i);
            }
            users.removeAll(Arrays.asList(baseUsers));
            // 创建房间            
            System.out.println("create room success");          
           
        }
    }
}

测试

这里是每增加一个用户匹配一次，事实上match方法应该是一个类似监听器

@Test
 public  void matchUser() throws InterruptedException {
     int type = 0;
     BaseUser user1 = new BaseUser(1, "aa");
     BaseUser user2 = new BaseUser(2, "bb");
     BaseUser user3 = new BaseUser(3, "cc");
     Match.put(user1, type);
     Match.match();
     Match.put(user2, type);
     Match.match();
     Match.put(user3, type);
 }

最后显示的结果为

  startMatch
匹配自选模式人数为：1
startMatch
匹配自选模式人数为：2
startMatch
[cn.slycmiaoxi.match.BaseUser@21001, cn.slycmiaoxi.match.BaseUser@c5e0b1, cn.slycmiaoxi.match.BaseUser@fa7b71]
create room success

最后说明

1.至于取消匹配，做法类似
2.现实中匹配要考虑好多因素，可以想象LOL中的匹配~
当然目前只是一个简单的demo，仅供参考！