CEDEC 2020 Speakers Interview Series Vol.3 Collision Aware Multi-Phase Multi-Layer 3D Path Search

Luminous Productions’ developers took the stage at CEDEC2020 (Computer Entertainment Developers Conference 2020), which was held online in September, 2020. Through this interview series, we will be revealing additional details along with the speakers’ thoughts and sentiments behind the development.

Facebook Share Twiiter Share Linkedin Share Reddit Share Tumblr Share

■The speaker of [Collision Aware Multi-Phase Multi-Layer 3D Path Search]

Could you start off by giving us a brief overview of your talk?

Tsai : The nature of my talk was more that of a lecture than a typical session, I should say, as I briefly went through everything that is required in order to implement a path-finding algorithm in a 3D space starting from the basics. I also talked about the collision- and congestion-avoiding features I implemented and how I did it.

What made you to choose this subject?

Tsai : While 2D path-finding has been quite mainstream up until now, I was thinking that 3D space mobility is also crucial for objects that are in the air. Right around then, I heard about the call for CEDEC speakers and my supervisor recommended that I give it a try, which is what kick-started the whole thing. The quality of movement of such characters as NPCs or enemies, which are not controlled by the player, heavily depend on the path-finding system in use. With just 2D path-finding, it can only respond to objects that exist on the ground, resulting in an unrealistic look. To solve this problem, I wanted to create a path that enables non-playable characters to move in 3D space like an actual human being.

Would you say that path-finding is essential because it directly leads to improving the quality of the game itself?

Tsai : Yes, path-finding will continue to be an important element in the future particularly in open world games, where the environment presents characters with abilities to travel across various types of terrains, rather than just simply walking on the ground, as well as enemy characters with many different ecological characteristics.

Was there anything in your research that you found particularly challenging?

Tsai : Generally speaking, 3D path-finding is often implemented in a simplified manner. In other words, its focus is only on finding the shortest path and travelling with the shortest travel time. However, I constructed an overarching path plan for the implementation for my research this time, so that when an object moves, it does so while avoiding the paths of other objects in advance and plans a comprehensively good path. It might be easier to understand if you think of an airplane as an example. Airplanes use the radar to measure where other planes are located, and from the get-go they choose their path based on avoiding collision, right? That’s basically what I created.

I’d assume that would require high level algorithms as well – did that in particular pose any difficulty?

Tsai :Let’s see, I come from the electronics industry originally, not the game industry. An electronic device contains tons of circuits, and what’s in those circuits is a path, or rather, an electronic current line. A single unit of CPU has more than thousands of circuits. That’s what I specialized in originally, so I basically took and implemented a technology from the electronics industry. While these are two different fields, their aims remain the same, and what path-finding does is establish a route while making concessions with other agents. There are, however, minor differences in detailed requirements and solutions.

So in both the electronics and game industry, path-finding is required to establish an optimal route that can avoid collision?

Tsai :Once the problem is simplified, we all want the optimal, best possible path whether it’s in circuits or in games, right? That being said, as there are multiple paths running at the same time, just having an individual optimal path doesn’t mean it’s the best solution. The best solution is having a “comprehensively good outcome.” Even then, we need to define what should be considered “comprehensively good.” In my talk, I also presented methods for comprehensive evaluation.

Will changing the evaluation methods allow the feature to function in various different situations as well?

Tsai : Yes, that is correct. For example, if you want all of the agents to travel the shortest possible distance, you should arrange the evaluation in a way that the shortest distance is recognized as optimal, in which case all of the agents will selfishly travel through the shortest path. If you want the agents to make concessions with each other, structure the evaluation as such to allow them room to wiggle. Such evaluation formulae are very important.

Are such evaluation values pre-determined to a certain extent? Or, did you establish them through trial-and-error by experimenting?

Tsai : It required tons of experimentation and testing. With my testing patterns, I determined the evaluation values after creating thousands of maps and having thousands of human characters travel through them to get a clear understanding of what that would look like, where they would collide, and how long the paths would end up becoming.

It sounds like highly versatile research.

Tsai : It really is. For example, even though it’s not gaming, map applications use the same technology. It’s capable of doing things like loading the map all at once, calculating the shortest possible path, and avoiding obstacles.

Were there any other aspects of your research that you found particularly difficult?

Tsai : Like I said earlier, my original research area is electronic circuits, but this time, I worked on a game. As such, what I found difficult was that these two fields have different requirements. With electronic circuits, an overlap of lines causes a short circuit, whereas that’s perfectly acceptable in games. You can always go through the same crossover point as long as you shift the timing of line overlapping, right? It was time consuming to process a minor discrepancy in a set of requirements and adjust how the structure is designed.

Did you work on your research by yourself?

Tsai : I read up on research papers from previous CEDEC and GDC sessions and also used how other researchers went about with their work as a reference when going forward with mine. In addition, as my coworkers at Luminous Productions (LP) have vast experience, I went to them for an insight on what is in demand, what the problems are and what we are looking for in future implementations and so forth.

■The past and present of [AI] in the game industry – the future of path-finding

What is your view on path-finding using AI?

Tsai : This is just my personal opinion, but until a little while ago, when people in the game industry used the word “AI”, they were referring to “any and everything that humans haven’t done,” but now the term mainly refers to “machine learning.” In that sense, I could say that the “AI” in my research is from old times as it works in accordance with the algorithm that I determine. Machine learning, on the other hand, can conduct hundreds of thousands of trial-and-error on its own and eventually become capable of finding paths like humans do, so I personally believe the latter is better and that’s what will be the mainstream going forward. Using AI just to establish the shortest path is a waste, but, for example, with the “find a comprehensively good path” evaluation I configured there is a limit to what the current algorithm can do, so it’d be a good choice to leave whatever the algorithm can’t do to AI.

Do you think that path-finding using machine learning will be achieved in the near future?

Tsai : Given that AI development is progressing so rapidly, I believe it’s very possible that just one research paper or talk will singlehandedly outperform the old-time algorithms, and that sort of development can emerge from one of the major game studios. The bigger the scale of the game is, the more resources the studio can offer, and the more teams capable of conducting such research, the better the chances are. In addition, as video games in general are getting closer than ever to the real world, tools from the real world are becoming more and more available. Therefore, technologies that are used in other fields, such as map applications, are very likely to be adopted in games in the future.

How would you like to further advance your research going forward?

Tsai : I was only able to work on the fundamentals this time, so I hope to work more on putting the feature into actual practice. I touched upon this subject during my talk as well, but I want to work more on what connects 2D and 3D, like “running and flying at the same time” or “diving into water while still running” for example. I hope to be able to show the various phases that exist in a path in a natural way. Ideally, I will accomplish more elaborate path-finding and actually implement it.

Does your ideal seem feasible so far?

Tsai : Personally I think so yes, because for the Luminous Engine we create our own tools. A challenge like this only came true, because LP engages in development of both the engine and the game - an environment like this is truly valuable. Furthermore, at LP, we have experts specializing in various fields such as rendering technology and QA technology. I believe we’ll be able to create something incredible if we all work together to combine our skills. Hopefully, my research will be of benefit as well.

Lastly, do you have any message for the audience of your talk as well as the readers of this interview?

Tsai : I’m hoping to build path-finding through collective effort, with everyone. In other industries, researchers often build upon research outcomes discovered by other researchers and they work together to promote advancement. The game industry, however, is unique in that sense, as people tend to work on theirs individually. In this talk, all I did was propose one definition and benchmark; I certainly hope people will try out different implementation methods using the same requirements I used, and bring forth even better outcomes – that will give me motivation for my next endeavor. In the electronics field, there are conferences in different research areas every year where engineers can compete with each other on their performance and capabilities. Hopefully, one day we’ll get to have an opportunity where we can compete with each other using aspects such as the path length, the level of congestion, and calculation speed as evaluation criteria.


Facebook Share Twiiter Share Linkedin Share Reddit Share Tumblr Share