A Map Complexity Measure Based on Contact Surface

Yan Li; Wen Ju Zhao; Zhen Hua Zhou

doi:10.4028/www.scientific.net/AMM.411-414.1994

Paper Titles

Rule Acquisition Based on Inconsistent Decision-Making Information System
p.1975

The Realization of Genetic Algorithm in Terms of Checkers Evaluation Function
p.1979

Training Neural Networks by Continued Fractional Weight Functions
p.1986

The Complexity Analysis for Game Map Based on the Summation of XOR
p.1990

A Map Complexity Measure Based on Contact Surface
p.1994

Research on Neural Networks Used in Parallel Computing
p.1998

An AHP-Based Fuzzy Approach for Evaluation of Index System on Coordinated Development of Ethnic Regions in China
p.2002

A Negative Selection Algorithm Base on the Self R-Tree
p.2007

The Algorithm Animation of Genetic Algorithm of Travelling Salesman Problem
p.2013

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 411-414A Map Complexity Measure Based on Contact Surface

A Map Complexity Measure Based on Contact Surface

Abstract:

This paper defined the full connect map and contact surface, and proposed a new map complexity measure, and compared with measurement methods based on Hamming distance and relative Hamming distance. We further research on the relationship between the complexity measure and the map connectivity. The complexity measures based on Hamming distance and contact surface are applicable to full connectivity map, and the new measurement can reflects the difficulty of the pathfinding algorithm more accurately, especially in a higher complexity.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 411-414)

Pages:

1994-1997

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.411-414.1994

Citation:

Cite this paper

Online since:

September 2013

Authors:

Yan Li, Wen Ju Zhao, Zhen Hua Zhou

Keywords:

Complexity Measure, Contact Surface, Hamming Complexity, Pathfinding

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] P. Hart, N. Nilsson, B. Raphael: A formal basis for the heuristic determination of minimum cost paths . IEEE Transactions on Systems Science and Cybernetics. Vol. 4(1968), pp.100-107.

DOI: 10.1109/tssc.1968.300136

Google Scholar

[2] A. Botea, M. Muller and J. Shaeffer: Near Optimal Hierarchical Path-Finding. Journal of Game Development. (2004), pp.7-28.

Google Scholar

[3] H. Samet: The Quadtree and Related Hierarchical Data Structures, ACM Computer Survival. vol. 16(1984), pp.187-260.

DOI: 10.1145/356924.356930

Google Scholar

[4] Su Pan, Li Yan, Li Wenliang: A Game Map Complexity Measure Based on Hamming Distance, Proc. of the 3rd International Conference on Computational Intelligence and Industrial Application(2010). (in Chinese).

Google Scholar

[5] Li Yan, Li Tiesong, Chen Cai, Su Lanming: Map Complexity Measurement Based on Relative Hamming Distance. Computer Engineering. (2012), pp.10-12.

Google Scholar