Search

The artificial intelligence (AI) of Non-Player Companions (NPC), especially opponents, is a key element to adjust the level of games in game design. Smart opponents can make games more challenging as well as allow players for diverse experiences, even in the same game environment. Since game users interact with more than one opponent in most of today's games, collaboration control of opponent characters becomes more important than ever before. In this paper, we introduce a cooperative strategy based on the A* algorithm for enemies' AI in the Pac-Man game. A survey from 17 human testers shows that the levels with our collaborative opponents are more difficult but interesting than those with either the original Pac-Man's personalities or the non-cooperative greedy opponents.

In the stealth game design, level designers are to develop many interesting game environments with a variety of difficulties. J. Tremblay and his co-authors developed a Unity-based level design tool to help and automate this process. Given a map, if the designer inputs several game factors such as guard paths and velocities, their vision, and the player's initial and goal positions, then the tool visualizes simulation results including (clustered) possible paths a player could take to avoid detection. Thus with the help of this tool, the designer can ensure in realtime if the current game factors result in the intended difficulties and players paths, and if necessary adjust the factors. In this note, we present our improvement on this tool in two aspects. First, we integrate a function that if the designer inputs some vertices in the map, then the tool systematically generates and suggests interesting guard paths containing these vertices of various difficulties, which enhances its convenience and usefulness as a tool. Second, we replace the collision-detection function and the RRT-based (player) path generation function, by our new collision-check function and a Delaunay roadmap-based path generation function, which remarkably improves the simulation process in time-efficiency.

In this paper, we propose an adaptive pavement region detection method that is robust to changes of structural patterns in a natural scene. In order to segment out a pavement reliably, we propose two step approaches. We first detect the borderline of a pavement and separate out the candidate region of a pavement using VRays. The VRays are straight lines starting from a vanishing point. They split out the candidate region that includes the pavement in a radial shape. Once the candidate region is found, we next employ the adaptive multi-seed region growing(A-MSRG) method within the candidate region. The A-MSRG method segments out the pavement region very accurately by growing seed regions. The number of seed regions are to be determined adaptively depending on the encountered situation. We prove the effectiveness of our approach by comparing its performance against the performances of seed region growing(SRG) approach and multi-seed region growing(MSRG) approach in terms of the false detection rate.

This paper proposes an efficient method that helps a visually impaired person to detect a pavement borderline. A pedestrian is equipped with a camera so that the front view of a natural scene is captured. Our approach analyzes the captured image and detects the borderline of a pavement in a very robust manner. Our approach performs the task in two steps. In a first step, our approach detects a vanishing point and vanishing lines by applying an edge operator. The edge operator is designed to take a threshold value adaptively so that it can handle a dynamic environment robustly. The second step is to determine the borderlines of a pavement based on vanishing lines detected in the first step. It analyzes the vanishing lines to form VRays that confines the pavement only. The VRays segments out the pavement region in a radial manner. We compared our approach against Canny edge detector. Experimental results show that our approach detects borderlines of a pavement very accurately in various situations.

Recently, the necessity for good techniques of detecting network traffic attack has increased. In this paper, we suggest a new method of detecting abnormal patterns of network traffic data by visualizing their IP and port information into two dimensional images. The proposed approach first generates four 2D images from IP data of transmitters and receivers, and makes one 2D image from port data. Analyzing those images, it then extracts their major features such as linear patterns or high intensity values, and determines if traffic data contain DDoS or DoS Attacks. To comparatively evaluate the performance of the proposed algorithm, we show that our abnormal pattern detection method outperforms the existing algorithm in terms of accuracy and speed.

In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line ℓ such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line ℓ is given in advance; we can solve this problem in time O(n log 2 n). In the case where only the direction of ℓ is fixed, we give an O(n2 log 2 n)-time algorithm. When ℓ is an arbitrary line, we give a randomized algorithm with expected running time O(n4 log 2 n). Then we present (1+ε)-approximation algorithms for these three problems. When we denote T(k, ε) = (k/ε2+(k/ε) log k) log (1/ε), these algorithms run in O(n log k + T(k, ε)) time, O(n log k + T(k, ε)/ε) time, and O(n log k + T(k, ε)/ε2) time, respectively. For k = O(n1/3/ log n), we also give randomized algorithms with expected running times O(n + (k/ε2) log (1/ε)), O(n+(k/ε3) log (1/ε)), and O(n + (k/ε4) log (1/ε)), respectively.

In this paper we study the problem of finding a set of k directions for a given simple polygon P, such that for each point [email protected]?P there is at least one direction in which the line through p intersects the polygon only once. For k=1, this is the classical problem of finding directions in which the polygon is monotone, and all such directions can be found in linear time for a simple n-gon. For k>1, this problem becomes much harder; we give an O(n^5log^2n)-time algorithm for k=2, and O(n^3^k^+^1logn)-time algorithm for fixed k>=3.

In this paper, we study a variant of the classical art-gallery problem, in which we require that each point of the art gallery is observed by two guards from nearly-opposite directions, ideally from front and back. We call a polygon P α-guarded by a set G of guards if every point p in P is visible from two guards g1,g2 in G satisfying α ≤ ∠g1pg2 ≤ π. We show that any simple n-gon is ⅔π-guarded by its n vertex guards, and there are simple n-gons that require at least n guards. Any simple n-gon can be (π – δ)-guarded by [Formula: see text] guards, and there are simple n-gons that require at least [Formula: see text] guards in any guard placement. We prove that the region of a simple n-gon that is α-guarded by k guards can have Θ(nk + k4) complexity in the worst case. Given simple n-gon P and k guard positions, we can decide for a fixed 0 < α < π whether P is α-guarded in O((nk2 + k4) log 2 nk) time and find the largest α < π for which P is α-guarded in O((nk2 + k4) log 6 nk) time.

We present a data structure for answering approximate shortest path queries in a planar subdivision from a fixed source. Let $\rho\geqslant1$ be a real number. Distances in each face of this subdivision are measured by a possibly asymmetric convex distance function whose unit disk is contained in a concentric unit Euclidean disk and contains a concentric Euclidean disk with radius $1/\rho$. Different convex distance functions may be used for different faces, and obstacles are allowed. Let $\varepsilon$ be any number strictly between 0 and 1. Our data structure returns a $(1+\varepsilon)$ approximation of the shortest path cost from the fixed source to a query destination in $O(\log\frac{\rho n}{\varepsilon})$ time. Afterwards, a $(1+\varepsilon)$-approximate shortest path can be reported in $O(\log n)$ time plus the complexity of the path. The data structure uses $O(\frac{\rho^2n^3}{\varepsilon^2}\log\frac{\rho n}{\varepsilon})$ space and can be built in $O(\frac{\rho^2n^3}{\varepsilon^2}(\log\frac{\rho n}{\varepsilon})^2)$ time. Our time and space bounds do not depend on any other parameter; in particular, they do not depend on any geometric parameter of the subdivision such as the minimum angle.