Thursday, May 4, 2017

Personal Project: Remaking Motherboard -> Bridges

Why?

I'm remaking my Motherboard game because of a few reasons:

- One majoy coding error that disables a piece from being moved outright.
- The complaint that it's only 4 player and only with XBox controllers.
-  The pathfinding algorithm being way too simple and illogical.

That's why I'm going from this:

Original Motherboard Game
 To This:

New Motherboard Game

Here's what I got so far:


I've written a script that can dynamically rewrite the strings that it uses to access the Unity Input Manager. There you can also generate anything from '1' to 'as-many-input-device-as-you've-set-up'.

For mouse controls, currently it's only one. So any of the 4 players can be setup with the one mouse (or all players with the one mouse, if you want), but seeing as how it's possible for games like "JamesTown" to do it merits more research.

The keyboards are a lot easier. I've picked out combinations of keys that make sense accros the keyboard and made sure none of them overlapped. The you can plug in 4 keyboards into the computer and, as long as each player only touches his own buttons, play with up to 4 players.

Like so


Controllers are handled by unity's Input Manager.


Pathfinder

The pathfinding algorithm is a lot more complex this time. Previously the AI made a very simple decision on the fly: if he could go straight, he does straight. If not, he would check if he could go left. If that was possible, he'd turn 90° to the left and move ahead. If not he'd try the same for the right side. If non of the above were available it meant that he had reached the end of the line and fell off of the level.

The new one is a lot more complex, as it calculates the shortest route possible to the furthest away point possible. Watch the video first.

First the NPC spawns a node at it's own position. Then that node check to three right of it using a Raycast down. If it hit nothing but an block it spawns another node at that position. Same for his left, up and down positions. Here's where it gets interesting: each  of those checks gets an int, 0 to 4. So the right check gets 0, left gets 1, up gets 2, down gets 3. As it spawns a node it gives it that int to add to an array of ints, and the node uses that array to identify itself; that becomes it's name. Then it goes trough the process again but not only does that node give a new node it's int, but also all the ints that the spawning node has in it's array. So, if this node's array is [0], and the node is spawned above this one, that nodes identifying array becomes [0,2]; it's parents + it's own.

Next the NPC checks all the nodes for the one that has the longest array of ints, for example Node N with identifiers [0,0,2,0,1,0,3,3,0,1,1,2,0]. Having the longest array means being the product of the most nodes, means being furthers away from the starting node.

The it compares all the other nodes' identifier arrays and sees if they match for every int in the array. For example you have a node A [0,0,2,0,1] and a node B [0,0,2,1,1,0,3,3]. Node A would need to check it's 5 ints to the 5 ints in node N (comparing 0=0, 0=0, 2=2, 1=1) and if they all match up that that node is one of the nodes that contributed to the furthest away node. If we do the same for node B we see that somewhere (0=0, 0=0, 2=2, 1=0, 1=1, 0=0, 3=3, 3=3) the iterations differ, meaning that at least one of it's parents came from a node spawned in a different iteration (the right, left, up, down checks), and so isn't a parent of the node N, and isn't part of the longest path.

All nodes that match are placed in a list, shortest identifier array to longest, starting with the node spawned by the NPC and finished with the furthest away node N. That list of nodes is the shortest route to the furthest away point possible.

Lastly the NPC moves to the second node in that list (the first node being at the same position as the NPC, so it would just stay in place), and then it runs the calculation again to allow the players to change the blocks around and build new possible paths.

Reprecussions:

The players used to have to consider the twists and turns of their path more than the destination. They could influence the NPC and stop it from going a route by doing the 4 checks in their head. That's why I added a blue trail before the NPC that worked on the exact same logic, just faster; doing an entire spawn-death cycle in one frame.

Now that trail is part of the pathfinding algorithm, and is visually a lot more interesting to see. The players also don't have to worry about losing all of their building progress because on one mis-rotated block halfway and the pathfinder prioritising that block. Now they can be sure that the path thet they're building is that path that is being taken, and now players can compete about where the NPC can go by individually building the longest path.

More to follow.

No comments:

Post a Comment