KR20010113673A

KR20010113673A - 휴대용 포켓 비디오 게임 시스템에 사용하기 위한 패턴 및심벌 런 렝스 인코딩을 기초로 한 데이터 압축/압축 해제

Info

Publication number: KR20010113673A
Application number: KR1020017009801A
Authority: KR
Inventors: 사미르 아보우-삼라; 클라우드 코마이어; 로버트 샴페인; 선 첸 팸; 프라산나 갈리; 스테픈 리; 준 팬; 씬 리
Original assignee: 야마우치 히로시; 닌텐도가부시키가이샤
Priority date: 1999-12-03
Filing date: 2000-11-30
Publication date: 2001-12-28
Also published as: JP2003515406A; US6416410B1; EP1157472A1; CA2361651A1; WO2001041312A1; AU1806501A

Abstract

휴대용 포켓 비디오 게임 시스템과 같은 제한된 리소스 환경에서 특히 유용한 비손실 데이터 압축/압축 해제는 대화식 사용자 입력에 응답하여 실시간으로 필요한 만큼 효율적이고 빠르게 압축 해제되어야 할 그래픽 및/또는 속성 데이터를 허용한다. 2 레벨 런 렝스 인코딩이 중복 패턴 및 중복 심벌을 코딩하는데 사용된다. 보통의 센티널 필드 포맷은 필드에 뒤이은 데이터가 비중복 데이터, 심벌 런, 또는 패턴 런 인지를 코딩한다. 전형적인 심벌 맵핑된 비디오 디스플레이 그래픽/속성 파일에 대하여 60%의 압축비를 얻을 수 있다.

Description

휴대용 포켓 비디오 게임 시스템에 사용하기 위한 패턴 및 심벌 런 렝스 인코딩을 기초로 한 데이터 압축/압축 해제{DATA COMPRESSION/DECOMPRESSION BASED ON PATTERN AND SYMBOL RUN LENGTH ENCODING FOR USE IN A PORTABLE HANDHELD VIDEO GAME SYSTEM}

비디오 게임의 세계는 단일 반도체 집적 회로 칩상에 배치될 수 있는 증가된 양의 처리 능력에 따라서 변화해왔다. 바로 몇 년전까지만 해도 고가의 아케이드 비디오 시스템에서만 이용될 수 있었던 게임이 이제는 저가의 휴대용 포켓 비디오 게임 시스템에서도 플레이 될 수 있다.

닌텐도사의 GAME BOY®및 GAME BOY COLOR®휴대용 비디오 게임 시스템이 최근에 매우 인기를 얻게 되었다. 이들 포켓용 시스템은 매우 소형이고 저렴한($100이하)패키지로 인상적인 대화식 비디오 게임 플레이를 제공한다. 이들 시스템에 대한 게임 개발자가 직면하는 도전중 하나는 재미있고 흥미로우며 더욱 더 정교해지고 복잡한 게임을 개발하여 이들 시스템이 제공하는 매우 제한된 메모리 및 프로세싱 리소스내에서 동작하는 가이다.

하나의 예로서, GAME BOY COLOR®에서 어드벤쳐 게임을 구현하기를 원한다고 가정한다. GAME BOY COLOR®의 디스플레이 메모리는 액정 디스플레이가 한 번에 표시할 수 있는 스크린보다 몇 배(예를 들면, 4~ 8배) 큰 배경 캐릭터 맵을 저장한다. 이것에 의해 보다 큰 가상 디스플레이 영역(예를 들면, 어드벤쳐 게임에서의 배경 또는 "레벨")에서 디스플레이 "윈도우"를 부드럽게 스크롤할 수 있게 된다. 그러나 수 백가지의 이미지 스크린을 포함하는 확장 배경에서 부드러운 스크롤을 할 수 있는 매우 흥미있는 어드벤쳐 게임을 만들기를 원한다고 가정한다. GAME BOY COLOR®의 제한된 디스플레이 메모리는 한 번에 너무나 많은 스크린의 이미지 정보를 저장할 수 없으며, 이러한 많은 스크린의 이미지 정보를 게임 카트리지에 저장하는 것은 많은 양의 롬 공간을 필요로 할 것이다. 이 문제를 해결하는 하나의 방법은 데이터 압축을 사용하여 이미지가 보다 작은 공간을 차지하도록 이미지 데이터를 변형하는 것이다.

이미지는 많은 저장 공간을 차지할 수 있기 때문에, 데이터 압축은 컴퓨터 그래픽에서 특히 중요하다. 컴퓨터 기술자는 그래픽 파일에 대한 다양한 데이터 압축 기술을 개발해왔다. 그래픽 파일에 적용해 왔던 다양한 압축 기술의 유용한 개론은 머레이등의그래픽 파일 포맷(1996, O'Reilly & Associates, 제 2판)의 페이지 153~218의 9장("데이터 압축")에서 찾을 수 있다.

일반적으로, 압축하는 동안 데이터 손실이 발생하지 않는 비손실(lossless) 압축과, 일부 데이터가 손실되며 압축된 데이터에 결합되지 않는 손실(lossy) 압축의 2가지의 데이터 압축 방법이 있다. 일반적으로, 2가지 유형의 데이터 압축 기술 모두 다 압축된 이미지에서의 데이터 중복의 양을 줄이는 것에 의존한다. 데이터 압축은 데이터 파일의 사이즈를 줄이는데 사용되는 데이터 코딩의 한 유형이다. 코드로서 알려진, 순환 캐릭터 또는 패턴을 보다 짧은 심벌로 변환하는 방법을 인코딩이라 부른다. 원래의 캐릭터 또는 패턴으로 코드를 역변환하는 방법을 디코딩이라 부른다. 과거에 일반적으로 사용되었던 그래픽 파일을 압축하는데 사용되는 하나의 간단하지만 효율적인 데이터 압축 기술을 런 렝스 인코딩(run length encod ing)이라 부른다. 런 렝스 인코딩은, 예를 들면, TIFF, BMP 및 PCX와 같은 범용 비트맵 그래픽 파일 포맷에 의해 지원된다. 런 렝스 인코딩은 심벌(예를 들면, 캐릭터)의 반복되는 스트링의 물리적 사이즈를 줄이는 것으로서 작용한다. "런(run)"이라 불리는, 이 반복 스트링은 보통 2바이트로 코딩된다. "런 카운트 (run count)"라 불리는, 제 1의 바이트는 런에서 심벌의 수를 나타낸다. "런 값 (run value)"이라 불리는, 제 2의 바이트는 (ASCII 캐릭터에 대한 이진수 0~ 255의 범위의) 런에서 심벌의 값이다. 예를 들면, 15 "A" 캐릭터("AAAAAAAAAAAAAAA")의 캐릭터 런은 저장하는데 보통 15바이트가 필요 할 것이다. 런 렝스 인코딩후에 동일한 스트링은 단지 2 바이트("15A")만 필요할 것이다.

많은 데이터 압축 작업을 과거부터 해 왔지만, 보다 향상된 것이 가능하다. 특히, 런 렝스 인코딩 기술과 관련하여 간단하며, 능률적이고, 낮은 오버헤드를 갖지만, 캐릭터가 맵핑된 이미지 및 속성 데이터에 특히 적합하고 휴대용 포켓 비디오 게임 시스템과 같은 제한된 리소스 시스템에서 효율적인 이미지 압축 해제가 가능한 데이터 압축 및 압축해제가 필요하다.

본 발명은 데이터 압축/압축 해제, 특히 이미지 데이터의 압축 및 압축 해제에 관한 것이다. 보다 상세히 본 발명은 휴대용 포켓 비디오 게임 시스템과 같은 제한된 리소스 환경에서 캐릭터가 맵핑된 그래픽 데이터의 효율적이며 빠른 비손실 압축 해제를 제공하기 위한 패턴 및 심벌(예를 들면, 캐릭터)의 런 렝스 인코딩 (run length encoding)에 관한 것이다.

도 1은 종래 기술의 휴대용 포켓 비디오 게임 시스템을 나타낸 도면.

도 2a는 도 1 시스템의 블럭도.

도 2b는 도 1 시스템의 디스플레이 RAM의 메모리 맵.

도 2c는 보다 큰 가상 배경 캐릭터 맵에서 스크롤하는 도 1 시스템의 디스플레이 영역을 나타낸 도면.

도 3은 본 발명의 바람직한 실시예에 의해 제공되는 전반적인 압축/압축 해제 방법을 나타낸 도면.

도 4는 센티널 필드 포맷을 나타낸 도면.

도 5는 패턴 필드 포맷을 나타낸 도면.

도 6은 압축 방법의 흐름도.

도 7은 압축 해제 방법의 흐름도.

도 8은 도 7의 압축 해제 방법동안의 판독 및 기록 포인터 조작을 나타낸 도면.

도 9는 도 7의 압축 해제 방법을 사용한 간이형 비디오 게임 프로그램을 나타낸 도면.

본 발명은 입력 이미지 파일을 조사하고 보다 짧은 심벌에 의해 표현될 수 있는 심벌의 패턴의 반복뿐만이 아니라 심벌의 반복을 찾음으로써 전형적인 런 렝스 인코딩을 보강하는 새롭고 향상된 데이터 압축 기술을 제공한다. 이 멀티 레벨 압축 기술은 소량의 오버헤드 데이터만을 사용하여 상당히 효과적으로 수행될 수 있어서 최종적으로 압축된 이미지 데이터가 경제적인 휴대용 포켓 비디오 게임 시스템과 같은 프로세싱 및 메모리가 강요된 환경의, 런 타임"시작점"에서, 효과적으로 압축 해제될 수 있다. 그러한 비손실 데이터 압축/압축 해제는, 대화식 사용자 입력에 응답하여 실시간으로 효과적이고 빠르게 압축 해제되어야 할 그래픽 및/또는 속성 파일을 허용하기 때문에, 휴대용 포켓 비디오 게임 시스템과 같은 제한된 리소스 환경하에서 특히 유용하다.

바람직한 실시예에 있어서, 보통의 "센티널(sentinel)" 필드 포맷은 필드에 뒤이은 데이터가 비중복 데이터, 심벌 런, 또는 패턴 런인지를 코딩한다. 전형적인 캐릭터가 맵핑된 비디오 디스플레이 그래픽/속성 파일에 대한 60%의 압축비를 얻을 수 있다.

본 발명의 하나의 측면에 따른 데이터 압축 방법은 패턴 및 심벌 중복을 검출하기 위해 입력 파일을 스캔하며, 스캐닝 단계가 패턴 중복을 알리면, 상기 패턴중복을 런 렝스 인코딩하고 상기 런 렝스 코딩된 패턴 중복을 출력 파일에 기록하며; 스캐닝 단계가 심벌 중복을 알리면, 상기 심벌 중복을 런 렝스 인코딩하고 상기 런 렝스 코딩된 심벌 중복을 상기 출력 파일에 기록하며; 스캐닝 단계가 심벌 중복과 패턴 중복 둘 다 알리지 않으면, 비중복 정보를 상기 출력 파일에 기록하는 단계로써 특징지어진다.

데이터 압축 해제 방법은 어떠한 (a)패턴 중복과, (b)심벌 중복도 가리킬 수 있는 설정된 데이터 포맷을, 입력 파일에서, 판독하며; 설정된 데이터 포맷이 패턴 중복을 가리키면, 상기 설정된 데이터 포맷과 관련된 중복 패턴 런을 런 렝스 디코딩하며; 설정된 데이터 포맷이 심벌 중복을 가리키면, 상기 설정된 데이터 포맷과 관련된 중복 심벌 런을 런 렝스 디코딩하며; 설정된 데이터 포맷이 패턴 중복과 심벌 중복 둘 다를 가리키지 않으면, 상기 설정된 데이터 포맷과 관련된 비중복 데이터를 판독하는 단계로서 특징지어진다.

설정된 데이터 포맷은 중복 또는 비중복을 가리키는 제 1의 필드와 심벌 중복이 존재하면 중복 심벌의 수를 가리키는 제 2의 필드를 포함하는 센티널 필드 포맷을 포함할 수 있으며, 상기 제 1 및 제 2의 필드의 값은 스캐닝 단계가 패턴 중복을 알리면 설정된 값으로 함께 코딩된다.

본 발명에 의해 제공되는 상기 및 그 밖의 특징 및 장점은 첨부된 도면과 함께 바람직한 실시예의 아래의 상세한 설명을 참조함으로써 보다 명백히 이해될 것이다.

종래 기술의 칼러 비디오 게임 칼러 시스템의 일반적인 설명

도 1은 칼러 액정 디스플레이(LCD:16)상에 게임 캐릭터를 표시하는 닌텐도 (Nintendo)사의 GAME BOY COLOR®로서 알려진 종래 기술의 휴대용 칼러 디스플레이 게임 시스템(10)을 나타낸다. 시스템(10)에 의해 실행되어야 할 특정 비디오 게임또는 그 밖의 프로그램을 공급하는, 메모리 장치 기반 카트리지(12)를 시스템(10)이 인식한다. 다른 게임 또는 그 밖의 애플리케이션은 다른 카트리지(12)를 삽입함으로써 플레이 될 수 있다.

시스템(10)은 사용자로부터 대화식 입력을 수신하는 다양한 오퍼레이팅 키 (48a-48e)를 포함한다. 오퍼레이팅 키(48a)는 칼러 LCD(16)에 표시되는 게임 캐릭터를 4방향, 즉 위, 아래, 좌, 우로 움직이도록 지시하는데 사용된다. 오퍼레이팅 키(48b)는, 예를 들면, 게임 모드 선택등과 같은 것을 위해 사용되는 선택 키이다. 오퍼레이팅 키(48c)는 게임을 시작하거나 게임 진행을 일시적으로 중단하는데 사용되는, 소위 스타트 키이다. 오퍼레이팅 키(48d 및 48e)는 푸쉬 버튼 스위치이다. 오퍼레이팅 키(48d 및 48e)를 작동 시킴으로써, 칼러 LCD(16)상에 표시되는 게임 캐릭터의 다양한 움직임, 예를 들면, 무기 사용, 점프등과 같은 것을 표시하는 것이 (플레이되는 특정 게임에 따라) 가능하다. 오퍼레이팅 키(48a-48e)가 도 1에 나타낸 것과 같이 칼러 디스플레이 게임기(10)의 전면에 배치되며, 시스템(10)은 디스플레이(16)상에 해당 캐릭터 및 배경 움직임을 만들기 위해 실시간으로 이들 키 (48)의 작동에 응답한다.

종래 기술의 시스템(10)의 블럭도인 도 2a는 도트 메트릭스 디스플레이로서 제공되는 칼러 LCD(16)를 포함하는 칼러 디스플레이 게임 시스템(10)을 나타낸다. 칼러 LCD(16)는 칼러 이미지를 표시하도록 LCD 드라이버(22 및 24)에 의해 구동된다. LCD 드라이버(22)는, 예를 들면, LCD(16) 도트 메트릭스의 행을 선택적으로 구동하고, LCD 드라이버(24)는, 예를 들면, LCD 도트 메트릭스의 열을 선택적으로 구동한다. CPU(26)에 포함되는 칼러 디스플레이 처리 회로(28)로부터 칼러 이미지 신호가 LCD 드라이버(22 및 24)에 공급된다. CPU(26)는 내부 ROM(32) 및 내부 RAM (34)에 접속되는 CPU 코어(30)를 더 포함한다. CPU(26)는 공칭 속도(nominal speed ) 2.10MHZ의 발진 신호를 공급하는 기본 수정 발진기(36) 및 연동된 주파수 디바이더(38)를 더 포함한다.

커넥터(40)는 적절한 버스(41)에 의해 CPU(26)에 접속된다. 카트리지(12)는 커넥터(40)에 선택적으로 부착된다. 카트리지(12)는 외부 ROM(42) 및 SRAM(46)을 포함한다. ROM(42)은 비디오 게임 프로그램 명령 및 데이터를 저장한다. 각 카트리지의 SRAM(46)은 게임의 백업 데이터를 저장하는데 사용된다. 카트리지(12)로부터 공급되는 게임 프로그램 및 캐릭터 데이터와, 오퍼레이팅 키(48a- 48e)로부터 공급되는 컨트롤러 데이터에 따라, CPU(26)는 데이터 처리 연산을 수행하고 필요시 확장 RAM(50)을 사용하여, 디스플레이 데이터를 디스플레이 RAM(52)에 기록한다. 전체적으로 디스플레이 RAM(52)은 칼러 LCD(16)의 스크린에서 디스플레이를 위, 아래 및/또는 좌, 우로 스크롤 할 수 있는, 칼러 LCD(16)의 디스플레이 영역보다 큰 저장 영역을 갖는다.

종래 기술의 도 2b는 디스플레이 RAM(52)의 메모리 맵이다. 디스플레이 RAM (52)은 각각이 두 개의 디스플레이 메모리를 포함하는 두 개의 뱅크로 나누어 질 수 있다. 이 예에서, 디스플레이 RAM(52)은 캐릭터 맵핑 기능, 즉 디스플레이 RAM (52)에도 저장된 캐릭터 코드에 따라 디스플레이(16)에 맵핑되는 캐릭터 "스탬프" 또는 "타일"을 저장하는 것을 수행한다. 이 예에서, 타일 각각은 칼러 LCD 디스플레이(16)의 8×8 픽셀로서 형성되는 64도트 영역으로서 한정된다. LCD 디스플레이의 디스플레이 범위의 종래 기술인 도 2c 맵에 나타낸 것과 같이, LCD 디스플레이 (16)는 160픽셀의 너비와 144픽셀의 높이여서, 8×8 픽셀 배경 타일로 동시에 20 ×18=360개를 표시할 수 있다.

이 예에서, 배경 캐릭터에 대한 타일 데이터는 디스플레이 RAM(52)에 기록되며, LCD(16) 디스플레이 공간상에 이 타일 데이터를 캐릭터 맵핑하는데 사용되는 캐릭터 코드/속성 데이터도 디스플레이 RAM(52)에 기록된다. 도 2c에 나타낸 것과 같이, 디스플레이 메모리(52)는 32×32 타일 캐릭터 맵중 어떠한 곳에서도 LCD 디스플레이(16)를 포함하는 20×18 타일 "윈도우"를 부드럽게 스크롤 할 수 있도록 칼러 LCD(16)에 의해 동시에 표시 가능한 타일의 수(360)보다 훨씬 큰 타일의 수 (1024)에 해당하는 저장 용량을 가질 수 있다. 일반적으로, 타일 데이터 및 속성 데이터는 초기에 카트리지(12)에 저장되며, 표시를 위해서 CPU(26)에 의해 디스플레이 메모리(52)로 전송된다.

압축 기술의 이점없이, 카트리지(12)는 디스플레이 RAM(52)의 배경 캐릭터 맵으로서의 저장을 위해 각각이 1024Kbyte(즉, 1.024Mbyte)의 사이즈를 갖는 그래픽 및 속성 파일을 공급해야 한다. 많은 배경 스크린을 갖는 복잡한 게임때문에, 단지 그래픽 데이터만을 저장하기 위해 요구되는 카트리지 저장 공간의 양이 과도해 질 수 있다. 데이터 압축이 데이터 파일 및 속성 파일을 압축하는데 사용될 수 있지만, CPU(26)에 의해 제공되는 제한된 처리 리소스가 대화식 게임 플레이와 관련된 그 밖의 작업을 수행하는 것으로 종종 점유되며, 사용자는 압축 해제되어야할 새로운 이미지 및 속성 화일에 대한 지연을 게임 플레이 중 격는 것을 원하지 않을 것이기 때문에, 이미지 및 속성 화일의 사이즈를 줄이는데 사용되는 어떠한 데이터 압축 기술도 매우 효율적으로 압축을 해제해야 한다.

본 발명의 바람직한 실시예에 따른 압축 기술

본 발명은 시스템(10)의 리소소가 제약된 환경에서 빠르며, 능률적이고, 낮은 오버헤드 압축 해제를 가능케 하는 런 렝스 인코딩을 기초로 한 압축 기술을 제공한다.

도 3은 본 발명의 바람직한 실시예에 따른 압축/압축 해제 방법을 나타낸다. 예를 들면, 그래픽 이미지 및/또는 속성 데이터를 포함하는 입력 파일(100)은 압축 방법(200)에 의해 처리된다. 압축 방법(200)은 압축된 데이터 구조(300)를 만들기 위해 입력 파일(100)을 코딩한다. 압축된 데이터 구조(300)는, 예를 들면, 카트리지(12)의 롬(42)에 저장될 수 있다. 시스템(10)의 연산동안, 프로세서(26)는 카트리지(12)로부터 압축된 데이터 구조(300)를 판독하고 압축 해제 방법(400)을 사용하여 데이터 구조의 압축을 해제할 수 있다. 최종적으로 압축 해제된 데이터 파일 (100')은 디스플레이(16)에 표시하기 위해 이미지를 발생하는데 시스템(10)이 사용한다. 바람직한 실시예에 있어서, 압축 방법(200)은 비손실 방식이여서 압축 해제된 출력 파일(100')은 압축에 앞선 입력 파일(100)의 정확한 사본이다.

도 3은 압축된 데이터 구조(300)가 하나 또는 그 이상의 센티널 필드(320)와, 하나 또는 그 이상의 패턴 필드(340)와, 하나 또는 그 이상의 데이터 필드 (360)를 포함할 수 있는 것을 나타낸다. 입력 파일(100)의 컨텐츠에 따라, 압축된데이터 구조(300)에 다양한 필드(320, 340, 360)가 존재할 것이다. 바람직한 실시예에 있어서, 센티널 필드(320)는 런 렝스 인코드 중복 심벌(예를 들면, 캐릭터)에 사용되며, 패턴 필드(340)는 심벌의 런 렝스 인코드 중복 패턴(예를 들면, 캐릭터 패턴)에 사용된다. 높은 중복도를 갖지 않는 데이터 필드(360)는 바람직한 실시예에 의해 코딩되지 않지만, 때로는 런 렝스 인코딩 기술(즉, "압축되지 않은" 입력 파일과 관련있는 "압축된" 출력 파일의 사이즈를 실제적으로 증가(또는 적어도 감소시키지 않는)시키는 "압축"에 의해 도입되는 오버헤드)과 연관된 네거티브 압축비를 피하기 위해서 코딩되지 않은 형태로 압축 방법(200)에 의해 패스된다. 압축된 파일(300)에서 각각의 파일(320, 340, 360)중 하나보다 많을 수 있다.

센티널 필드

도 4는 본 발명의 바람직한 실시예에 의해 제공되는 센티널 필드(320)를 나타낸다. 센티널 필드(320)는 바람직한 실시예에 있어서 1바이트(8 비트)이며, 플래그(322)와, 넘버 필드("S":324)인 두 개의 동일하지 않은 부분을 갖는다. 바람직한 실시예에 있어서, 센티널 필드(320)는 그것에 뒤이은 데이터가 중복 캐릭터 런, 중복 심벌 런, 또는 둘 다 아닌 지를 가리키는데 사용된다.

바람직한 실시예에 있어서, 플래그(322)는 데이터 중복이 검출되었는지를 판단하는데 사용된다. 바람직한 실시예의 플래그(322)의 사이즈는 1비트이다. 바람직한 실시예에서는 플래그(322)로서 센티널 필드(320)의 최상위 비트를 사용하며, 중복이 검출되었다는 것을 가리키기 위해 플래그를 "1"로, 반대의 경우에는 "0"으로 셋팅한다.

바람직한 실시예에 있어서, 넘버 필드(324)는 센티널 필드(320)의 나머지(즉, 바람직한 실시예에서 비트 0부터 6까지)를 점유한다. 넘버 필드(324)에 저장된 값은 센티널 필드(320)에 의해 코딩되는 중복 또는 유일한(즉, 비중복) 바이트의 수를 가정한다. 특히, 플래그(322)는 유일한 값을 코딩하면(즉, 플래그=0), 넘버 필드(324)는 얼마나 많은 비반복 심벌이 센티널 필드(320)에 뒤이은 지를 가리킨다. 플래그(322)는 중복을 코딩하면(즉, 플래그=1), 넘버 필드(322)는 심벌이 얼마나 많이 반복되어야 하는 지를 가리킨다. 바람직한 실시예에서 표현될 수 있는 중복 또는 유일한 바이트의 최대수는 127이다.

또 다른 필드(360 또는 340)가 바람직한 실시예의 센티널 필드(320)에 뒤이은다. 이 또 다른 필드의 컨텐츠는 센티널 필드(320)의 컨텐츠에 의해 좌우된다. 플래그(322)가 비중복의 값(예를 들면, 플래그=0)을 가리키면, 뒤이은 필드는 넘버 필드(324)에 의해 지시되는 렝스의 비중복 심벌의 스트링을 포함하는 데이터 필드 (360)를 포함한다. 플래그(322)가 중복의 값(플래그=1)을 코딩하면, 뒤이은 필드는 반복되어야 할 심벌을 포함하는 1 바이트의 데이터 필드(360)를 포함한다.

넘버 필드(324)가 (제로 중복 또는 비중복의 심벌을 가리키는) 0으로 셋팅되면, 이것은 센티널 필드(320)에 바로 뒤이은 정보가 중복이 아니거나 또는 비중복의 데이터인 것을 가리키지만, 대신에 패턴 필드에 뒤이은 패턴 런을 코딩하는데 사용되는 패턴 필드(340)를 포함하는, 특별한 경우도 바람직한 실시예는 포함한다.

바람직한 실시예의 패턴 필드(340)

도 5는 본 발명의 바람직한 실시예에 따른 패턴 필드(340)를 나타낸다. 상술한 바와 같이, 특별한, 모두 0인 형태의 센티널 필드(320)가 선행함으로써 패턴 필드(340)가, 압축된 데이터 구조(300)에서 제공되는 것을 바람직한 실시예는 나타낸다. 바람직한 실시예에 있어서, 패턴 필드(340)의 사이즈는 1 바이트이다. 바람직한 실시예에 있어서, 패턴 필드(340)는 각각이 4비트인 두 개의 동일한 부분(342 및 344)으로 이루어진다. (높은 니블, 즉 비트 4~7 일 수 있는) 제 1의 부분 "PS" (342)이 중복 패턴의 렝스를 바이트로 코딩한다. 바람직한 실시예에서는 이 정보를 코딩하기 위해 4 바이트를 사용하기 때문에, 바이트의 최대 패턴 사이즈는 15가 될 것이다. 제 2의 부분"S"(342)(낮은 니블, 즉 바람직한 실시예에서 비트 0~3)은 패턴의 중복 값, 즉 패턴이 몇 번이나 반복되어는지를 코딩한다. 바람직한 실시예에서는 중복 값을 저장하기 위해 4비트를 사용하기 때문에, 표현될 수 있는 최대 값은 15이다. 바람직한 실시예에 있어서, 필드(342)에 의해 포함되는 값 "PS"에 해당하는, 바이트의 렝스를 갖는 중복 패턴 심벌 스트링을 포함하는 데이터 필드(360)가 패턴 필드(340)에 뒤이은다. 이 데이터 필드(360)는 "S"필드(344)에 의해 지시되는 회수만큼 반복되는 패턴을 저장한다.

데이터 압축 방법(200)

도 6은 본 발명의 바람직한 실시예에 의해 제공되는 압축 방법(200)의 단계의 흐름도이다. 방법(200)은 입력 파일(100)을 압축하기 위해 2개의 패스를 사용한다. 제 1의 패스(블럭(206-210))는 중복 패턴을 검출하고 코딩하는데 사용된다. 제 2의 패스(블럭(212-218))는 중복 데이터를 식별하고 비중복 데이터로부터 중복 데이터를 분리, 즉 중복 심벌을 식별하고 코딩하는데 사용된다.

바람직한 실시예의 제 2의 패스는 심벌이 연속해서 적어도 3번 발견되는 지를 검사하는 검사(214)를 포함한다. 검사(214)는 단지 연속해서 적어도 3번 발견되는 지를 발견하면 중복이 되어야 할 심벌을 선언한다. 따라서, 검사(214)는 심벌이 단지 한 번 반복되면 런 렝스 인코딩과 관련된 오버헤드가 방법(200)중 발생하지 않도록 방지한다. 바람직한 실시예에서 단지 한 번 반복되는 심벌을 압축하는 것은 어떠한 데이터도 축소되지 않지만 부가적인 코딩 복잡도를 만들기 때문에, 바람직한 실시예의 압축 방법(200)은 데이터를 비중복 데이터로서 취급하고 어떠한 코딩도 없이 그러한 데이터를 "그 자체로서" 통과시킨다.

바람직한 실시예에 있어서, 각 제 1의 패스 스캔은, 패턴 필드(342)의 중복 값에 대한 최대 값이 15바이트 사이즈를 가진 15이기 때문에 최대 225바이트로 구성된다. 우리가 패턴 필드(340)를 코딩하기 위해 2바이트를 사용하면, 값 225은 65025바이트까지 커질수 있다. 이러한 다른 장치에 있어서, 1 바이트 필드(342)는 패턴의 사이즈를 저장하기 위해 사용되며, 1바이트 필드(344)는 패턴이 반복되는 회수(즉, 중복 값)를 저장하기 위해 사용될 수 있다. 바람직한 실시예에서는 중복 또는 유일할 바이트의 수를 가리키기 위해 7비트 센티널 필드 수의 값(324)을 사용하기 때문에, 단지 다음의 128바이트만 제 2의 패스중에 스캔될 것이다.

다음은 (결정 블럭(204)에 의해 테스트되면서) 입력 파일(100)의 끝까지 루프되는, 도 6 흐름도에 나타낸 바람직한 실시예 방법의 보다 상세한 설명이다.

1. 다음의 225바이트를 스캔하고 패턴 중복을 검출하시오(블럭(206 및 208)). 패턴 필드(340)는 15바이트 사이즈의 최대 15중복을 홀딩할 수 있기 때문에, 바람직한 실시예에서 225바이트 보다 크게 스캔할 필요가 없다.

2. 패턴 중복이 발견되면(결정 블럭(208)에 "예" 존재), 중복 패턴을 코딩하는 적절한 센티널 필드(320), 패턴 필드(240) 및 데이터 필드(260)를 대상 파일 (300)에 기록하고(블럭(210)) 단계 1로 가시오(블럭 204).

3. 다음 127 바이트를 스캔하고 렝스 3 또는 그 이상의 심벌 중복을 검출하시오(블럭(212 및 214)). 센티널 필드(320)는 127의 최대 값을 홀딩할 수 있기 때문에, 한 번에 127바이트 보다 크게 스캔할 필요가 없다. 저장하는데 2 바이트가 들기 때문에, 블럭(214)은 원래 데이터와 같은 사이즈인 렝스 2의 중복을 거절할 것이다.

4. 중복이 발견되면(결정 블럭(214)에 "예"존재), 중복 심벌을 코딩하는 적절한 센티널 필드(320) 및 데이터 필드(360)를 대상 파일에 기록하고(블럭(216)) 단계 1로 가시오(블럭(204)).

5. 중복이 발견되지 않으면(결정 블럭(214)에 "아니오"존재), 코딩없이 비 중복 심벌을 패스하는 적절한 센티널 필드(320) 및 데이터 필드(360)를 대상 파일에 기록하고(블럭(218)) 단계 1로 가시오(블럭 204).

압축 예

다음은 도 6에 나타내며 상기에 기술된 바람직한 실시예의 방법에 의해 수행되는 데이터 압축의 일 예이다.

61바이트 사이즈의 원래 파일:

0xDE 0xAE 0x2E 0x0C 0x55 0x21 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE 0xDE 0xDE 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA

0xDE 0xDA 0xDE 0xDA 0xDE 0xDE 0xA8 0x2E 0x0f 0x54 0x21

0xDD 0xAA 0x22 0xFC 0x66 0x26

검출 타입에서 강조하기 위해 다시 타이핑되는 원래 파일

유일한 바이트

0xDE 0xAE 0x2E 0x0C 0x55 0x21

중복

0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE

패턴

0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA

유일한 바이트

0xDE 0xA8 0x2E 0x0f 0x54 0x21 0xDD 0xAA 0x22 0xFC 0x66

26바이트 사이즈의 압축된 파일(300)(뚜렷함을 위해서, 센티널 필드(320)는 2진수로 나타내며, 패턴 필드(340)는 따옴표 사이에 16진수로 나타내며, 데이터 필드(360)는 16진수로 나타낸다).

유일한

0000010 0xDE 0xAE 0x2E 0x0C 0x55 0x21

중복

10011111 0xDE

패턴

00000000 '0x26' 0xDA 0xDE

유일한

00001100 0xDE 0xA8 0x2E 0x0f 0x54 0x21 0xDD 0xAA 0x22

0xFC 0x66 0x26

바람직한 실시예의 압축 해제 방법(400)

도 7은 본 발명의 바람직한 실시예에 의해 제공되는 압축 해제 방법(400)의 흐름도이다. 바람직한 실시예의 압축 해제 방법(400)은, 센티널 필드에 뒤이은 정보가 코딩되며 어떻게 코딩되었는지를 가리키기 위해 센티널 필드(320)에 의존한다. 압축 파일(300)의 처음에 위치되는 제 1의 센티널 필드(320)를 사용하여, 방법(400)은 적절한 데이터를 대상(압축되지 않은) 파일(100')에 기록하며 다음 센티널 필드로 움직일 것이다.

센티널 필드(320)는, 압축된 파일(300)을 판독하는 동안 얼마나 많은 판독 파일 포인터(402)가 움직여야 하는지로써 판단하며, 동시에 판독 파일 포인터(402)를 다음 센티널 필드로 위치를 정한다(도 8참조). 센티널 필드(320)의 최상위 비트가 1로 셋팅되고 넘버 필드(324)에 뒤이은 값 "S"(즉, 비트 0에서 비트 6까지의 다음 7비트)가 0보다 크면, 판독 파일 포인터(402)는, 대상 파일(100')에 'S'번으로 씌어질 다음 바이트로 움직일 것이다. 센티널 필드(320)의 최상위 비트가 0으로 셋팅되고 넘버 필드(324)의 비트 0부터 비트 6까지의 다음 7비트의 값 'S'가 0보다 크면, 판독 파일 포인터(402)는 컨텐츠를 대상 파일(100')에 기록하는 동안 다음 'S'바이트로 움직일 것이다(다시 말해서, 판독 파일 포인터(402)는 다음 S바이트를 대상 파일에 복사할 것이다). 센티널 필드(320)의 제 1의 7비트의 값(즉, 비트 0~ 6)이 0이면, 다음 바이트는 패턴 런을 코딩하는 패턴 필드(340)일 것이다. 패턴 필드(340)가 상위 4비트에서 발견되는 패턴 사이즈'PS'(필드(342))와, 4비트의 수이며 패턴 필드(340)의 하위 4비트(필드(344))에서 발견되는 패턴 중복 값'S'를 홀딩한다. 이 경우에, 다음 'PS'바이트는 대상 파일(100')에 'S'번으로 씌어질 것이다.

다음은 (결정 블럭(408)에 의해 테스트되면서, 압축된 파일(300)의 끝에 도달할 때까지 루프되는) 도 7 방법의 보다 상세한 설명이다.

1. 센티널 필드 플래그(322)의 컨텐츠(센티널 필드(320)의 비트 7)를 '플래그'로, 센티널 필드의 나머지(비트 0~ 6, 즉 넘버 필드(324))를 'S'로 판독하시오(블럭 410).

2. 'S'의 값이 패턴 런을 가리키는 0과 같으면(결정 블럭(412)에 "예"존재), 단계 8로 가시오(블럭(422)).

3. 플래그의 값이 비중복 심벌 스트링을 가리키는 0이면(결정 블럭(414)에 "예"존재), 단계 6으로 가시오(블럭(416)).

4. 중복 심벌 런을 디코딩하기 위해, 1바이트로써 판독 파일 포인터(442)를증가시키고(블럭(418)) 센티널 필드 'S'번에 뒤이은 데이터 블럭의 컨텐츠를 대상 파일(100')에 기록하시오(블럭(420)).

5. 파일(300)의 다음 센티널 필드로 가리키기 위해 파일 포인터를 증가시키고(블럭(428)) 단계 1로 가시오(블럭(408)).

6. 비중복 심벌 스트링을 판독하기 위해, 해당 데이터 블럭을 대상 파일에 기록하면서 파일 포인터'S'번을 증가시키시오.

7. 파일(300)의 다음 센티널 필드로 가리키도록 파일 포인터를 증가시키고(블럭(428)) 단계 1로 가시오(블럭(408)).

8. 패턴 런을 디코딩하기 위해, 파일 포인터를 증가시키고, 상위 4비트의 값을 'PS'로, 하위 4비트의 값을 'S'로 셋팅하시오(블럭(424)).

9. 파일 포인터 'PS'번을 증가시키고 뒤이은 데이터 블럭 컨텐츠 'S'번을 대상 파일에 기록하고(블럭(426)), 단계 1로 가시오(블럭(408)).

압축 해제 예

다음은, 도 7에 나타낸 바람직한 실시예의 압축 해제 방법이 어떻게 압축된 파일(300)을 압축 해제된 데이터 파일(100')로 압축을 해제하는데 사용될 수 있는지의 일 예이다.

26바이트 사이즈의 압축된 파일(뚜렷함을 위해서, 센티널 필드(320)은 2진수 로, 패턴 필드(340)는 따옴표사이에서 16진수로, 데이터 필드(360)는 16진수로 나타낸다).

유일한

00000110 0xDE 0xAE 0x2E 0x0C 0x55 0x21 (압축됨)

제 1의 센티널 필드(320)의 플래그(322)가 0이기 때문에, 렝스 6의 유일한(비중복) 시퀀스로 번역하며 번역은 다음과 같이 될 것이다:

0xDE 0xAE 0x2E 0x0C 0x55 0x21 (압축 해제됨)

중 복

10011111 0xDE

센티널 필드(320)의 플래그(322)가 1이기 때문에, 렝스 31의 중복으로 번역하며 번역은 다음과 같이 될 것이다:

0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE (압축 해제됨)

패턴

00000000 '0x26' 0xDA 0xDE (압축됨)

센티널 넘버 필드(324)의 값이 0과 같기 때문에, 다음 필드는 패턴 필드 (340)이며, 이 경우에, 패턴 필드는 우리가 6번 반복되는 렝스 2바이트의 패턴 중복을 갖는 것을 가리키며, 번역은 다음과 같이 될 것이다:

0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA

0xDE (압축 해제됨)

유일

00001100 0xDE 0xA8 0x2E 0x0f 0x54 0x21 0xDD 0xAA 0x22

0xFC 0x66 0x26 (압축됨)

센티널 필드(320)의 플래그(322)가 0이기 때문에, 렝스 12의 유일한(비중복)시퀀스로 번역하며 번역은 다음과 같이 될 것이다:

0xDE 0xA8 0x2E 0x0f 0x54 0x21 0xDD 0xAA 0x22 0xFC 0x66

0x26 (압축해제됨)

모든 압축 해제된 시퀀스를 결합함으로써, 우리는 어떠한 데이터의 손실 없이 원래의 파일(100)을 복원한다.

61 바이트 사이즈의 원래 파일

0xDE 0xAE 0x2E 0x0C 0x55 0x21 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE 0xDE

0xDE 0xDE 0xDE 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA 0xDE 0xDA

0xDE 0xDA 0xDE 0xDA 0xDE 0xDE 0xA8 0x2E 0x0f 0x54 0x21

0xDD 0xAA 0x22 0xFC 0x66 0x26

압축비 결과

본 발명의 바람직한 실시예를 사용하여 얻을 수 있는 압축 비율은 압축되는 입력 데이터 파일(100)의 개별적인 특성에 의존할 것이다. 각 2048 바이트 사이즈의 1650 샘플 GAME BOY COLOR®그래픽/속성 파일의 테스트에 기초하여, 우리가 얻은 평균 압축 비율은 대략 60%였다.

최악의 경우에, 본 발명의 압축 기술의 애플리케이션은 압축되지 않은 파일 (100)과 관련있는 압축된 파일(300)의 사이즈를 실질적으로 증가시킬수 있다. 그러한 예에서, 압축되지 않은 파일(100)을 "그 자체로서" 어떠한 코딩도 가하지 않고 대상 방법에 통과시키는 것이 바람직할 수 있다.

도 7의 압축 해제 방법을 사용한 비디오 게임

압축 해제 방법(400)은 카트리지 ROM(42)에 저장된 소프트 웨어의 제어아래서 대화식 비디오 게임 플레이를 하는 동안 실시간으로 시스템(10)의 프로세서(26)에 의해 수행될 수 있다. 압축 해제 방법(400)은, 예를 들면, 비디오 게임 소프트웨어의 부분으로서 카트리지(12)에 저장된 소프트웨어 프로그램으로 실시될 수 있다. 도 9는 (예를 들면, 이동 물체 캐릭터를 레벨 또는 랜드스케이프 근처로 움직임으로서) 대화식 게임 플레이를 하는 동안 카트리지 ROM(42)에서의 파일을 동적으로 복사하며, RAM(34 및/또는 50)에서 버퍼링하며, 표시를 위해 디스플레이 RAM (52)에 기록하는 전반적인 방법에서 필요한 만큼 그래픽 및 속성 파일을 압축 해제하기 위해 도 7 압축 해제 방법을 사용하는 간이형 비디오 게임(500)의 흐름도이다.

도 9를 참조하면, 부트 ROM(32)에 저장된 소프트웨어와 연계하여 비디오 게임 프로그램(500)은 시스템(10)을 초기하하고, 안전성 체킹등을 수행할 수 있다(블럭(504)). 비디오 게임 프로그램(500)은 카트리지 ROM(42)에 저장된 배경 및 이동 물체 캐릭터 그래픽 및 속성을 코딩하는 압축된 데이터 파일(300)을 판독하고, 도7과 관련하여 상기에 기술된 절차를 사용하여 이들 파일의 압축을 해제하고, 최종적으로 압축이 해제된 파일(100')을 시스템(10)으로써 표시하기 위해 디스플레이 RAM(52)에 저장한다(블럭(506)). 비디오 게임 프로그램(500)은 주기적으로 입력 제어(48)를 판독하고 이동 물체를 점프, 전투등을 함으로써 사용자 입력에 대화식으로 응답하며/응답하거나 디스플레이 RAM(52)에 의해 현재 저장된 배경 물체 캐릭터 맵과 관련있는 디스플레이(16)의 윈도우를 스크롤함으로써 배경 물체와 관련있는 이동 물체를 움직인다(블럭(514)). 이동 물체가 디스플레이 RAM(52)에 의해 현재 저장된 배경 물체 캐릭터 맵과 관련있는 범위 밖으로 움직였을 경우에(결정 블럭 (510)에 "예"존재), 비디오 게임 프로그램(500)은 (다시 한번, 도 7 압축 해제 절차를 사용하여) 압축된 형태로 카트리지(12)에 의해 저장된 부가적인 배경 캐릭터 이미지 및 속성 파일(300)의 압축을 해제하고 최종적으로 압축이 해제된 이미지 및 속성 파일(100')을 시스템(10)으로써 표시하기 위해 디스플레이 RAM(52)에 기록 할 수 있다(블럭(512)). 도 7 압축 해제 방법(400)은 충분히 효율적이며 고속이어서 압축 해제는 시스템(10)의 사용자에게 성가실 수 있는 상당한 딜레이를 발생하지않고 필요한 만큼 실시간으로 수행될 수 있다. 블럭(508-514)의 방법은 게임이 끝날때까지 계속될 수 있다(블럭(516 및 518)).

본 발명은 현재 가장 실용적이고 바람직한 실시예로 고려되는 것에 관하여 기술되었지만, 본 발명은 개시된 실시예에서 제한되지 말아야하며, 첨부된 청구항의 범위에 포함되는 다양한 수정 및 동등한 장치를 커버하려는 것이 이해되어야 한다. 예를 들면, 본 명세서에 개시된 데이터 압축 및 압축 해제 기술이 캐릭터가 맵핑된 비디오 게임 그래픽 및/또는 속성 데이터에 특히 유용하지만, 이 기술은 텍스트, 사운드, 이미지, 코드 또는 그 밖의 데이터를 포함하는 모든 유형의 데이터를 압축/압축 해제하는데 사용될 수 있다.

Claims

적어도 하나의 이동 물체를 배경 캐릭터 맵에 표시하는 단계;

대화식 사용자 입력을 판독하고 상기 배경 캐릭터 맵과 관련있는 상기 이동 물체를 응답적으로 움직이는 단계;

상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는지를 검사하는 단계; 및

상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는 것을 상기 검사 단계가 알리면, 압축된 또 다른 배경 캐릭터 정보를 압축 해제하고 상기 압축 해제된 또 다른 배경 캐릭터 정보를 상기 배경 캐릭터 맵에 더하는 단계를 포함하며,

상기 압축 해제는 상기 압축된 또 다른 배경 캐릭터 정보에서 설정된 필드 포맷을 판독하는 단계와, 상기 필드에 뒤이은 정보가 적어도 하나의 비중복 심벌, 적어도 하나의 중복 심벌 또는 적어도 하나의 중복 패턴을 포함하는 것을 상기 필드 포맷이 가리키는지를 판단하기 위해 상기 필드 포맷을 검사하는 단계와, 상기 필드 포맷에 응답하여 상기 필드 포맷에 뒤이은 상기 정보를 디코딩하는 단계를 포함하는 것을 특징으로 하는 대화식 비디오 게임 플레이 방법.
배경 캐릭터 맵에서 적어도 하나의 이동 물체를 표시할 수 있는 액정 디스플레이;

상기 액정 디스플레이에 결합되는 프로세서;

상기 프로세서에 결합되며, 상기 배경 캐릭터 맵을 저장하는 디스플레이 메모리;

상기 프로세서에 결합되는 적어도 하나의 사용자 입력 장치; 및

상기 프로세서에 교환 가능하게 결합될 수 있으며, 압축된 또 다른 배경 캐릭터 정보를 저장하며, 대화식 사용자 입력을 판독하고 상기 배경 캐릭터 맵과 관련있는 상기 이동 물체를 응답적으로 움직이며; 상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는지를 검사하며; 상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는것을 상기 검사 단계가 알리면, 실시간 플레이 동안 상기 압축된 또 다른 배경 캐릭터 정보를 압축 해제하고 상기 압축 해제된 또 다른 배경 캐릭터 정보를 상기 디스플레이 메모리의 상기 배경 캐릭터 맵에 기록하기 위해서 프로세서를 제어하는 적어도 하나의 프로그램을 더 저장하는 휴대용 저장 매체를 포함하며,

상기 프로그램은 압축 해제하기 위해 상기 압축된 또 다른 배경 캐릭터 정보에서 설정된 필드 포맷을 판독함으로써 상기 프로세서를 제어하며, 상기 필드에 뒤이은 정보가 적어도 하나의 비중복 심벌, 적어도 하나의 중복 심벌 또는 적어도 하나의 중복 패턴을 포함하는것을 상기 필드 포맷이 가리키는지를 판단하고, 적어도 부분적으로 상기 필드 포맷에 기초한 상기 필드에 뒤이은 상기 정보를 디코딩하기 위해 상기 필드 포맷을 검사하는 것을 특징으로 하는 대화식 비디오 게임 시스템.
배경 캐릭터 맵의 적어도 하나의 이동 물체를 표시할 수 있는 액정 디스플레이와, 상기 액정 디스플레이에 결합되는 프로세서와, 상기 프로세서에 결합되며, 상기 배경 캐릭터 맵을 저장하는 디스플레이 메모리와, 상기 프로세서에 결합되는 적어도 하나의 사용자 입력 장치를 포함하는 대화식 비디오 게임 시스템과 함께 사용하기 위한, 상기 프로세서에 교환가능하게 결합될 수 있는 휴대용 저장 매체로서, 상기 휴대용 저장 매체는:

(a) 압축된 또 다른 배경 캐릭터 정보, 및

(b) 사용중인, 적어도 하나의 소프트웨어 프로그램을 저장하며, 상기 적어도 하나의 소프트웨어 프로그램은:

(b1) 상기 사용자 입력 장치로부터 대화식 사용자 입력을 판독하고 상기 배경 캐릭터 맵과 관련있는 상기 이동 물체를 움직이고;

(b2) 상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는지를 검사하고;

(b3) 상기 대화식 사용자 입력이 상기 이동 물체가 상기 배경 캐릭터 맵의 범위 밖으로 움직이도록 명령하는 것을 상기 검사 단계가 알리면, 실시간 비디오 게임 플레이동안 상기 압축된 또 다른 배경 캐릭터 정보를 압축 해제하고 상기 압축 해제된 또 다른 배경 캐릭터 정보를 상기 디스플레이 메모리의 상기 배경 캐릭터 맵에 기록하기위하여 프로세서를 제어하며,

상기 프로그램은 압축 해제하기 위해 상기 압축된 또 다른 배경 캐릭터 정보에서 설정된 필드 포맷을 판독함으로써 상기 프로세서를 제어하며, 상기 필드에 뒤이은 정보가 적어도 하나의 비중복 심벌, 적어도 하나의 중복 심벌 또는 적어도 하나의 중복 패턴을 포함하는것을 상기 필드 포맷이 가리키는지를 판단하고, 적어도 부분적으로 상기 필드 포맷에 기초한 상기 필드에 뒤이은 상기 정보를 디코딩하기 위해 상기 필드 포맷을 검사하는 것을 특징으로 하는 휴대용 저장 매체.
(a) 중복 심벌 및 중복 패턴을 위해 상기 그래픽 데이터를 스캔하는 단계;

(b) 센티널 필드를 사용하여 중복 심벌을 코딩하는 단계; 및

(c) 센티널 필드에 뒤이은 패턴 필드를 사용하여 중복 패턴을 코딩하는 단계를 포함하는 비디오 게임 그래픽 및/또는 속성 데이터를 압축하는 방법.
제 4항에 있어서, 상기 중복 심벌을 코딩하는 단계(b)는 중복 심벌 런 렝스를 코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 5항에 있어서, 상기 중복 패턴을 코딩하는 단계(c)는 중복 패턴 런 렝스를 코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 4항에 있어서, 상기 중복 패턴을 코딩하는 단계(c)는 중복 패턴 런 렝스를 코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 4항에 있어서, 상기 중복 심벌을 코딩하는 단계(b)는 심벌 중복이 존재하는지를 가리키기 위해 상기 센티널 필드의 플래그를 셋팅하는 단계를 포함하는 것을 특징으로 하는 방법.
제 8항에 있어서, 상기 플래그를 셋팅하는 단계는 단일 비트를 셋팅하는 단계를 포함하는 것을 특징으로 하는 방법.
제 4항에 있어서, 상기 센티널 필드를 사용하여 비중복 심벌 스트링을 코딩하는 단계를 더 포함하는 것을 특징으로 하는 방법.
(a) 중복 심벌을 위해 상기 그래픽 데이터를 스캔하는 단계;

(b) 상기 스캐닝 단계가 상기 그래픽 데이터의 중복 심벌에 위치하면, 센티널 필드 포맷을 사용하여 중복 심벌을 코딩하는 단계; 및

(c) 상기 스캔하는 단계가 상기 그래픽 데이터의 비중복의 심볼에 위치하면, 상기 센티널 필드 포맷을 사용하여 비중복 심벌을 코딩하는 단계를 포함하는 데이터 압축 방법.
(a) 센티널 필드를 위해 상기 파일을 스캔하는 단계;

(b) 상기 센티널 필드에 포함된 정보를 기초로 한 중복 심벌을 디코딩하는 단계; 및

(c) 상기 센티널 필드에 뒤이은 패턴 필드를 사용하여 중복 패턴을 디코딩하는 단계를 포함하는 압축된 비디오 게임 그래픽 및/또는 속성 파일을 압축 해제하는 방법.
제 12항에 있어서, 상기 중복 심벌을 디코딩하는 단계는 중복 심벌 런 렝스 코드를 디코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 13항에 있어서, 상기 중복 패턴을 디코딩하는 단계(c)는 중복 패턴 런 렝스 코드를 디코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 12항에 있어서, 상기 중복 패턴을 디코딩하는 단계(c)는 중복 패턴 런 렝스 코드를 디코딩하는 단계를 포함하는 것을 특징으로 하는 방법.
제 12항에 있어서, 상기 중복 심벌을 디코딩하는 단계(b)는 심벌 중복이 존재하는지를 가리키는 상기 센티널 필드의 플래그를 판독하는 단계를 포함하는 것을 특징으로 하는 방법.
제 16항에 있어서, 상기 플래그를 판독하는 단계는 단일 플래그 비트를 판독하는 단계를 포함하는 것을 특징으로 하는 방법.
제 12항에 있어서, 상기 센티널 필드를 사용하여 비중복 심벌 스트링을 디코딩하는 단계를 더 포함하는 것을 특징으로 하는 방법.
(a) 제 1 및 제 2의 센티널 필드 포맷을 위해 압축된 그래픽 데이터 파일을 스캔하는 단계;

(b) 상기 제 1의 센티널 필드 포맷을 사용하여 중복 심벌을 디코딩하는 단계; 및

(c) 상기 제 2의 센티널 필드 포맷을 사용하여 비중복 심벌을 디코딩하는 단계를 포함하는 데이터 압축 해제 방법.
중복 심벌 및 중복 패턴을 위해 상기 그래픽 데이터를 스캔하는 데이터 스캐너;

센티널 필드를 사용하여 중복 심벌을 코딩하는 중복 심벌 인코더; 및

센티널 필드에 뒤이은 패턴 필드를 사용하여 중복 패턴을 코딩하는 중복 패턴 인코더를 포함하는 비디오 게임 그래픽 및/또는 속성 데이터를 압축하는 장치.
제 20항에 있어서, 상기 중복 심벌 인코더는 중복 심벌 런 렝스를 코딩하는 것을 특징으로 하는 장치.
제 21항에 있어서, 상기 중복 패턴 인코더는 중복 패턴 런 렝스를 코딩하는것을 특징으로 하는 장치.
제 20항에 있어서, 상기 중복 패턴 인코더는 중복 패턴 런 렝스를 코딩하는 것을 특징으로 하는 장치.
제 20항에 있어서, 상기 중복 심벌 인코더는 심벌 중복이 존재하는지를 가리키기 위해 상기 센티널 필드의 플래그를 셋팅하는 플래그 세터를 포함하는 것을 특징으로 하는 장치.
제 24항에 있어서, 상기 플래그 세터는 단일 플래그 비트를 셋팅하는 것을 특징으로 하는 장치.
제 20항에 있어서, 상기 센티널 필드를 사용하여 비중복 심벌 스트링을 코딩하는 비중복 심벌 스트링 인코더를 더 포함하는 것을 특징으로 하는 장치.
중복 심벌을 위해 상기 그래픽 데이터를 스캔하는 스캐너;

상기 스캐너가 상기 그래픽 데이터의 중복 심벌에 위치하면 센티널 필드 포맷을 사용하여 중복 심벌을 코딩하는 중복 심벌 인코더; 및

상기 스캐너가 상기 그래픽 데이터의 비중복 심벌에 위치하면 상기 센티널 필드 포맷을 사용하여 비중복 심벌을 코딩하는 비중복 심벌 인코더를 포함하는 데이터 압축 장치.
센티널 필드를 위해 상기 파일을 스캔하는 스캐너;

상기 센티널 필드에 포함된 정보를 기초로 한 중복 심벌을 디코딩하는 중복 심벌 디코더; 및

상기 센티널 필드에 뒤이은 패턴 필드를 사용하여 중복 패턴을 디코딩하는 중복 패턴 디코더를 포함하는 압축된 비디오 게임 그래픽 및/또는 속성 파일을 압축 해제하는 장치.
제 28항에 있어서, 상기 중복 심벌 디코더는 중복 심벌 런 렝스 코드를 디코딩하는 것을 특징으로 하는 장치.
제 29항에 있어서, 상기 중복 패턴 디코더는 중복 패턴 런 렝스 코드를 디코딩하는 것을 특징으로 하는 장치.
제 28항에 있어서, 상기 중복 패턴 디코더는 중복 패턴 런 렝스 코드를 디코딩하는 것을 특징으로 하는 장치.
제 28항에 있어서, 상기 중복 심벌 디코더는 심벌 중복이 존재하는지를 가리키는 상기 센티널 필드의 플래그를 판독하는 플래그 판독기를 포함하는 것을 특징으로 하는 장치.
제 32항에 있어서, 상기 플래그 판독기는 단일 플래그 비트를 판독하는 것을 특징으로 하는 장치.
제 28항에 있어서, 상기 센티널 필드를 사용하여 비중복 심벌 스트링을 디코딩하는 비중복 심벌 디코더를 더 포함하는 것을 특징으로 하는 장치.
제 1 및 제 2 의 센티널 필드 포맷을 위해 압축된 그래픽 데이터 파일을 스캔하는 스캐너;

상기 제 1의 센티널 필드 포맷을 사용하여 중복 심벌을 디코딩하는 중복 심벌 디코더; 및

상기 제 2의 센티널 필드 포맷을 사용하여 비중복 심벌을 디코딩하는 비중복 패턴 디코더를 포함하는 데이터 압축 해제 장치.
중복 심벌을 위해 상기 그래픽 데이터를 스캔하는 수단;

상기 스캐너가 상기 그래픽 데이터의 중복 심벌에 위치하면 센티널 필드 포맷을 사용하여 중복 심벌을 코딩하는 제 1의 코딩 수단; 및

상기 스캐너가 상기 그래픽 데이터의 비중복 심벌에 위치하면 상기 센티널 필드 포맷을 사용하여 비중복 심벌을 코딩하는 제 2의 코딩 수단을 포함하는 데이터 압축 장치.
제 1 및 제 2의 센티널 필드 포맷을 위해 압축된 데이터 파일을 스캔하는 수단;

상기 제 1의 센티널 필드 포맷을 사용하여 중복 심벌을 디코딩하는 제 1의 디코딩 수단; 및

상기 제 2의 센티널 필드 포맷을 사용하여 비중복 심벌을 디코딩하는 제 2의 디코딩 수단을 포함하는 데이터 압축 해제 장치.
패턴 및 심벌 중복을 검출하기 위해 입력 파일을 스캔하는 단계;

상기 스캔하는 단계가 패턴 중복을 알리면, 상기 패턴 중복을 런 렝스 인코딩하고 상기 런 렝스 코딩된 패턴 중복을 출력 파일에 기록하는 단계;

상기 스캔하는 단계가 심벌 중복을 알리면, 상기 심벌 중복을 런 렝스 인코딩하고 상기 런 렝스 코딩된 심벌 중복을 상기 출력 파일에 기록하는 단계; 및

상기 스캔하는 단계가 심벌 중복 및 패턴 중복 모두를 알리지 않으면, 비중복 정보를 상기 출력 파일에 기록하는 단계를 포함하는 데이터 압축 방법.
제 38항에 있어서, 상기 기록하는 단계 각각은, 심벌 중복이 존재하면 중복 또는 비중복을 가리키는 제 1의 필드와 중복 심벌의 수를 가리키는 제 2의 필드를 포함하는 센티널 필드 포맷을 기록하는 단계를 포함하며, 상기 제 1 및 제 2의 필드중 적어도 하나의 값은 상기 스캔하는 단계가 패턴 중복을 알리면 설정된 값으로 코딩되는 것을 특징으로 하는 데이터 압축 방법.
어떠한 (a)패턴 중복과, (b)심벌 중복도 가리킬 수 있는 설정된 데이터 포맷을, 입력 파일에서, 판독하는 단계;

상기 설정된 데이터 포맷이 패턴 중복을 가리키면, 상기 설정된 데이터 포맷과 연관된 중복의 패턴 런을 런 렝스 디코딩하는 단계;

상기 설정된 데이터 포맷이 심벌 중복을 가리키면, 상기 설정된 데이터 포맷과 연관된 중복 심벌 런을 런 렝스 디코딩하는 단계; 및

상기 설정된 데이터 포맷이 패턴 중복과 심벌 중복 둘 다를 가리키지 않으면, 상기 설정된 데이터 포맷과 연관된 비중복 데이터를 판독하는 단계를 포함하는 데이터 압축 해제 방법.
제 40항에 있어서, 심벌 중복이 존재하면 중복 또는 비중복을 가리키는 상기 설정된 데이터 포맷의 제 1의 필드와 중복 심벌의 수를 가리키는 제 2의 필드를 검사하는 단계를 더 포함하며, 상기 제 1 및 제 2의 필드중 적어도 하나의 값은 상기 스캐닝 단계가 패턴 중복을 알리면 설정된 값으로 코딩되는 것을 특징으로 하는 데이터 압축 해제 방법.